算法 – 静态查找

先明确“查找”的几个定义：

查找

查找表：（同一类型的）数据元素（或记录）构成的集合，是一种灵活的数据结构；

静态查找表：只查找，不改变查找表；

动态查找表：需要在查找表中插入元素或删除元素，这类查找表就是动态查找表；

平均查找长度：查找的基本操作是将记录的关键字与给定值进行比较；为确定记录在查找表中的位置，比较次数的期望值称为查找算法在查找成功时的平均查找长度；

静态查找中常用的算法是顺序查找和二分法查找。

顺序查找

基本思路是从表的一端开始，逐个进行比较；对顺序存储方式和链式存储方式的查找表都适用；成功查找的平均次数约为表长的一半；表现在代码中，就是一个for循环

• 优点：算法简单，适用面广，对查找表的结构没有要求；
• 缺点：当查找表数据量比较大时，平均查找长度较大，查找效率较低；

JavaScript 实现

var arr = [3, 12, 4, 6, 9, 10, 1, 15];
console.log(find(9, arr));
function find(tar, arr) {
    for (var i = 0, len = arr.length - 1; i < len; i++) {
        if (tar === arr[i]) return i;
    }
    return -1;
}

二分法查找

使用二分法查找有个前提条件：需要查找表按照关键字递增/递减的方式排列；

基本思路：从查找表中间位置将查找表“拆分”为两个子表，通过目标值和中间位置值的大小来决定下一步去哪个子表继续查找，然后对符合的子表重复上面的拆分、比较操作；直到查找成功或子表为空时结束；

JavaScript 实现

var arr = [1, 3, 4, 6, 9, 10, 12, 15];
console.log(halfFind(9, arr));

function halfFind(tar, arr) {
    var low = 0, high = arr.length, mid;
 
    while (low <= high) {
        mid = parseInt((low + high) / 2);
        var midVal = arr[mid];
        if (tar === midVal) return mid;
        else if (tar < midVal) high = mid - 1;
        else low = mid + 1;
    }
    return -1;
}

mid = parseInt((low + high) / 2)

这一句是取数组的中间下标，JavaScript 中可能会出现小数，所以用 parseInt 转一下，其他强类型语言比如C#中，两个整数相除结果肯定为整数，不需要转型；
数组长度为偶数的时候，中间下标有两个，取哪个都可以，上面这句代码取的是后边的值；

优点：效率比顺序查找要高；

缺点：它要求查找表进行顺序存储并按关键字有序排列，需要插入或删除时，需要移动大量的元素；

适用于表不易变动，又经常查找的情况（静态查找表和变动频率不大的动态查找表）；

DEMO

我做了一个二分法查找的动态效果，没有考虑重复数字的情况，只在数组中找第一个出现目标数字的位置；具体点击这里查看；