一天一算法 - 二分查找

介绍

当我们想在一个数组中查找一个元素的时候，最简单的方法莫过于顺序查找了，不过顺序查找有一个致命的缺点，就是它的性能太低了，比如说在 N 个数据中查找一个指定的元素，其最好的情况是只比较一次就找到了元素，最差情况是比较了 N 次，这也就是说，其平均情况下的比较次数为 (1 + N) / 2。

之前一篇文章中我提到过，如果想提高一个算法的性能，自然而然的就会想到树这种数据结构，比如对于一个二叉树而言，N 个节点最多也就只有 lgN 层，所以树这种结构总能将一个时间复杂度为 N 的算法降低到 lgN。

二分查找法查找的过程其实就是就像在一个树中查找元素，因为它每次比较都可以将数组的规模降低一半。所以对于二分查找而言，查找一个元素最多只需要经过 lgN + 1 次比较。

---

实现

实现二分查找有两种方法，一种是递归实现方式，一种是非递归实现方式。首先，我们在看看以递归方法实现：

var binarySearch = function(value, low, high) {
    if (high < low) {
        return low;
    }

    var mid = low + Math.floor((high - low) / 2);
    var cmp = array[mid] - value;
    if (cmp < 0) {
        return binarySearch(value, mid + 1, high);
    } else if (cmp > 0) {
        return binarySearch(value, low, mid - 1);
    } else {
        return mid;
    }
};

注意，由于代码是由 JavaScript 实现的，对于数字而言，它只有一个 number 类型，不像其他高级语言有 int, float, double 具体的划分，所以我们需要利用 Math.floor() 对除法计算的值进行向下取整。

下面是非递归实现方式：

var binarySearch2 = function(value, low, high) {
    var lo = low,
        hi = high;

    while (lo <= hi) {
        var mid = lo + Math.floor((hi - lo) / 2),
            cmp = array[mid] - value;

        if (cmp > 0) {
            hi = mid - 1;
        } else if (cmp < 0) {
            lo = mid + 1;
        } else {
            return mid;
        }
    }

    return lo;
};

如果你用二分查找法去查找一个元素，如果那个元素的确存在于数组中，那很好理解，二分查找法会把那个元素的下标返回，但是如果那个元素不在数组中，我们的二分法又会返回什么呢？毫无疑问的是，它一定会返回一个下标给我们，不过返回的这个下标到底是大于要查找的那个元素还是小于要查找的那个元素呢？不妨来做个实验。

        var array = new ArrayList();

        for(var i = 1; i < 6; i++) {
            array.push(i);
        }
        array.push(7);
        array.push(8);
        array.push(9);

        var index = array.search(6);

很明显的，我们的数组是 [1,2,3,4,5,7,8,9], 如果我们要在数组中查找 6, 其查找过程如下:

第一次查找：low = 0, high = 7, mid = low + (high - low) / 2 = 3, 所以说 array[mid] = 4 < 6， 这个时候重置 low 和 high 的值， low = mid + 1 = 4, high = 7。

第二次查找： low = 4, high = 7, mid = low + (high - low) / 2 = 5, 因为 array[5] = 7 > 6,所以说需要重置 high 的值，low = 4, high = mid -1 = 4，由于这个时候仍然满足 low <= high， 所以查找过程仍会继续。

第三次查找： low = 4, high = 4, mid = low + (high - low) / 2 = 4，因为 a[mid] = 5 < 6， 所以这时候需要重新调整 low 的值，low = mid + 1 = 5，由于这时候已经不满足 low <= high， 所以跳出循环。

经过上面过程的讨论，你可能发现了，其实如果我们要查找的元素不在数组中的话，那么返回的元素恰好大于要查找元素。恰好的意思是说，这个元素是大于 key 的最小键。

---

拓展

有的时候，利用二分查找我们还可以实现一些其他的功能，比如大于等于 key 的最小键或者小于等于 key 的最大键。

在上面的讨论中我们已经证实了，利用二分查找法返回的下标必然是大于等于 key 的最小键，所以这个函数可以这么写：

this.ceiling = function(value) {
    var index = this.search(value);
    return this.get(index);
};

对于小于等于 key 的最大键，我们需要多做点判断，主要如下：

1. 利用二分法是否查找到了元素，如果查找到了直接返回。

2. 如果没有查找到元素，而且返回了一个元素，由上面我们知道，返回的元素一定是大于 key 的，所以需要进行判断，当前下标是否等于 0， 如果等于 0 则返回 -1， 因为当前数组中已经不可能存在小于 key 的元素。

3. 如果经过上述步骤还是没有任何返回值，那么只需要将查找到的 index -1 返回即可。这也很好理解，因为如果数组中没有查找到要搜寻的元素 key，而是查找到了大于 key 的最小键，所以这时候只需要将下标减 1 的数返回，那么这个数一定是小于 key 的最大数。

this.floor = function(value) {
    var index = this.search(value);

    if(array[index] === value) {
        return array[index];
    }

    if(index === 0) {
        return -1;
    }

    return array[index - 1];
};

---

总结

按理说，二分查找法已经非常好了，不过它有一个缺点就是要求待查找的数组必须是有序的。所以对于一个随机的数组而言，假设我们利用比较型排序算法，那么排序的时间复杂度为 O(NlgN), 然后进行查找时间复杂度为 O(lgN)。而且对于一个需要使用二分查找的数组来说，它插入元素的复杂度为 O(2N)。

所以，我们不得不去寻找一种方法，确保我们的插入和查找元素的时间复杂度都能保持在对数级别。我将会在接下来的文章中讲解这么一种方法，那就是构建二叉查找树。

最后，如果你想查看本篇文章的源代码，可以访问 我的 Github 。