介紹

當我們想在一個數(shù)組中查找一個元素的時候，最簡單的方法莫過于順序查找了，不過順序查找有一個致命的缺點，就是它的性能太低了，比如說在 N 個數(shù)據(jù)中查找一個指定的元素，其最好的情況是只比較一次就找到了元素，最差情況是比較了 N 次，這也就是說，其平均情況下的比較次數(shù)為 (1 + N) / 2。

之前一篇文章中我提到過，如果想提高一個算法的性能，自然而然的就會想到樹這種數(shù)據(jù)結(jié)構(gòu)，比如對于一個二叉樹而言，N 個節(jié)點最多也就只有 lgN 層，所以樹這種結(jié)構(gòu)總能將一個時間復(fù)雜度為 N 的算法降低到 lgN。

二分查找法查找的過程其實就是就像在一個樹中查找元素，因為它每次比較都可以將數(shù)組的規(guī)模降低一半。所以對于二分查找而言，查找一個元素最多只需要經(jīng)過 lgN + 1 次比較。

實現(xiàn)

實現(xiàn)二分查找有兩種方法，一種是遞歸實現(xiàn)方式，一種是非遞歸實現(xiàn)方式。首先，我們在看看以遞歸方法實現(xiàn)：

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 實現(xiàn)的，對于數(shù)字而言，它只有一個 number 類型，不像其他高級語言有 int, float, double 具體的劃分，所以我們需要利用 Math.floor() 對除法計算的值進行向下取整。

下面是非遞歸實現(xiàn)方式：

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;
};

如果你用二分查找法去查找一個元素，如果那個元素的確存在于數(shù)組中，那很好理解，二分查找法會把那個元素的下標返回，但是如果那個元素不在數(shù)組中，我們的二分法又會返回什么呢？毫無疑問的是，它一定會返回一個下標給我們，不過返回的這個下標到底是大于要查找的那個元素還是小于要查找的那個元素呢？不妨來做個實驗。

        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);

很明顯的，我們的數(shù)組是 [1,2,3,4,5,7,8,9], 如果我們要在數(shù)組中查找 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， 所以查找過程仍會繼續(xù)。

第三次查找： low = 4, high = 4, mid = low + (high - low) / 2 = 4，因為 a[mid] = 5 < 6， 所以這時候需要重新調(diào)整 low 的值，low = mid + 1 = 5，由于這時候已經(jīng)不滿足 low <= high， 所以跳出循環(huán)。

經(jīng)過上面過程的討論，你可能發(fā)現(xiàn)了，其實如果我們要查找的元素不在數(shù)組中的話，那么返回的元素恰好大于要查找元素。恰好的意思是說，這個元素是大于 key 的最小鍵。

拓展

有的時候，利用二分查找我們還可以實現(xiàn)一些其他的功能，比如大于等于 key 的最小鍵或者小于等于 key 的最大鍵。

在上面的討論中我們已經(jīng)證實了，利用二分查找法返回的下標必然是大于等于 key 的最小鍵，所以這個函數(shù)可以這么寫：

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

對于小于等于 key 的最大鍵，我們需要多做點判斷，主要如下：

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

2. 如果沒有查找到元素，而且返回了一個元素，由上面我們知道，返回的元素一定是大于 key 的，所以需要進行判斷，當前下標是否等于 0， 如果等于 0 則返回 -1， 因為當前數(shù)組中已經(jīng)不可能存在小于 key 的元素。

3. 如果經(jīng)過上述步驟還是沒有任何返回值，那么只需要將查找到的 index -1 返回即可。這也很好理解，因為如果數(shù)組中沒有查找到要搜尋的元素 key，而是查找到了大于 key 的最小鍵，所以這時候只需要將下標減 1 的數(shù)返回，那么這個數(shù)一定是小于 key 的最大數(shù)。

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];
};

總結(jié)

按理說，二分查找法已經(jīng)非常好了，不過它有一個缺點就是要求待查找的數(shù)組必須是有序的。所以對于一個隨機的數(shù)組而言，假設(shè)我們利用比較型排序算法，那么排序的時間復(fù)雜度為 O(NlgN), 然后進行查找時間復(fù)雜度為 O(lgN)。而且對于一個需要使用二分查找的數(shù)組來說，它插入元素的復(fù)雜度為 O(2N)。

所以，我們不得不去尋找一種方法，確保我們的插入和查找元素的時間復(fù)雜度都能保持在對數(shù)級別。我將會在接下來的文章中講解這么一種方法，那就是構(gòu)建二叉查找樹。

最后，如果你想查看本篇文章的源代碼，可以訪問 我的 Github 。