摘要：正文二分查找關(guān)于二分查找法二分查找法主要是解決在一堆數(shù)中找出指定的數(shù)這類問題。用二分查找法找尋上界與精確查找不同之處在于，精確查找分成三類大于，小于，等于目標數(shù)。

題目描述

給定一個有序的數(shù)組，查找某個數(shù)是否在數(shù)組中，請編程實現(xiàn)。

分析與解法

一看到數(shù)組本身已經(jīng)有序，我想你可能反應出了要用二分查找，畢竟二分查找的適用條件就是有序的。那什么是二分查找呢？

二分查找可以解決（預排序數(shù)組的查找）問題：只要數(shù)組中包含T（即要查找的值），那么通過不斷縮小包含T的范圍，最終就可以找到它。其算法流程如下：

一開始，范圍覆蓋整個數(shù)組。
將數(shù)組的中間項與T進行比較，如果T比數(shù)組的中間項要小，則到數(shù)組的前半部分繼續(xù)查找，反之，則到數(shù)組的后半部分繼續(xù)查找。
如此，每次查找可以排除一半元素，范圍縮小一半。就這樣反復比較，反復縮小范圍，最終就會在數(shù)組中找到T，或者確定原以為T所在的范圍實際為空。
對于包含N個元素的表，整個查找過程大約要經(jīng)過log(2)N次比較。

此時，可能有不少讀者心里嘀咕，不就二分查找么，太簡單了。

然《編程珠璣》的作者Jon Bentley曾在貝爾實驗室做過一個實驗，即給一些專業(yè)的程序員幾個小時的時間，用任何一種語言編寫二分查找程序（寫出高級偽代碼也可以），結(jié)果參與編寫的一百多人中：90%的程序員寫的程序中有bug（我并不認為沒有bug的代碼就正確）。

也就是說：在足夠的時間內(nèi)，只有大約10%的專業(yè)程序員可以把這個小程序?qū)憣?。但寫不對這個小程序的還不止這些人：而且高德納在《計算機程序設(shè)計的藝術(shù) 第3卷 排序和查找》第6.2.1節(jié)的“歷史與參考文獻”部分指出，雖然早在1946年就有人將二分查找的方法公諸于世，但直到1962年才有人寫出沒有bug的二分查找程序。

你能正確無誤的寫出二分查找代碼么？不妨一試，關(guān)閉所有網(wǎng)頁，窗口，打開記事本，或者編輯器，或者直接在本文評論下，不參考上面我寫的或其他任何人的程序，給自己十分鐘到N個小時不等的時間，立即編寫一個二分查找程序。

二分查找法主要是解決在“一堆數(shù)中找出指定的數(shù)”這類問題。

而想要應用二分查找法，這“一堆數(shù)”必須有一下特征：（1）存儲在數(shù)組中 （2） 有序排列
所以如果是用鏈表存儲的，就無法在其上應用二分查找法了。

至于是順序遞增排列還是遞減排列，數(shù)組中是否存在相同的元素都不要緊。不過一般情況，我們還是希望并假設(shè)數(shù)組是遞增排列，數(shù)組中的元素互不相同。

二分查找法在算法家族大類中屬于“分治法”，分治法基本都可以用遞歸來實現(xiàn)的，二分查找法的遞歸JS實現(xiàn)如下：

function bsearch(array,low,high,target)
{
    if (low > high) return -1;
    var mid = Math.floor((low + high)/2);
    if (array[mid]> target){
        return  bsearch(array, low, mid -1, target);
    } else if (array[mid]< target){
        return  bsearch(array, mid+1, high, target);
    }ese{return mid;}
        
}

不過所有的遞歸都可以自行定義stack來解遞歸，所以二分查找法也可以不用遞歸實現(xiàn)，而且它的非遞歸實現(xiàn)甚至可以不用棧，因為二分的遞歸其實是尾遞歸，它不關(guān)心遞歸前的所有信息。

function bsearchWithoutRecursion(array,low,high,target)
{
    while(low <= high)
    {
        var mid = Math.floor((low + high)/2);
        if (array[mid] > target){
            high = mid - 1;
        }else if (array[mid] < target){
            low = mid + 1;
        }else{
            return mid;
        }
    }
    return -1;
}

之前的都是在數(shù)組中找到一個數(shù)要與目標相等，如果不存在則返回-1。我們也可以用二分查找法找尋邊界值，也就是說在有序數(shù)組中找到“正好大于（小于）目標數(shù)”的那個數(shù)。
用數(shù)學的表述方式就是：
在集合中找到一個大于（小于）目標數(shù)t的數(shù)x，使得集合中的任意數(shù)要么大于（小于）等于x，要么小于（大于）等于t。

舉例來說：
給予數(shù)組和目標數(shù)
var array = {2, 3, 5, 7, 11, 13, 17};
var target = 7;
那么上界值應該是11，因為它“剛剛好”大于7；下屆值則是5，因為它“剛剛好”小于7。

用二分查找法找尋上界

function BSearchUpperBound(array,low,high,target)
{
    if(low > high || target >= array[high]) return -1;
    
    var mid = (low + high) / 2;
    while (high > low)
    {
        if (array[mid] > target){
            high = mid;
       } else{
            low = mid + 1; 
       }
        mid = (low + high) / 2;
    }

    return mid;
}

與精確查找不同之處在于，精確查找分成三類：大于，小于，等于（目標數(shù)）。而界限查找則分成了兩類：大于和不大于。
如果當前找到的數(shù)大于目標數(shù)時，它可能就是我們要找的數(shù)，所以需要保留這個索引，也因此if (array[mid] > target)時 high=mid; 而沒有減1。

用二分查找法找尋下界

function BSearchLowerBound(array,low,high,target)
{
    if(high < low  || target <= array[low]) return -1;
    
    var mid = (low + high + 1) / 2; //make mid lean to large side
    while (low < high)
    {
        if (array[mid] < target){
            low = mid;
        }else{
            high = mid - 1;
        }
        mid = (low + high + 1) / 2;
    }

    return mid;
}

下屆尋找基本與上屆相同，需要注意的是在取中間索引時，使用了向上取整。若同之前一樣使用向下取整，那么當low == high-1，而array[low] 又小于 target時就會形成死循環(huán)。因為low無法往上爬超過high。
這兩個實現(xiàn)都是找嚴格界限，也就是要大于或者小于。如果要找松散界限，也就是找到大于等于或者小于等于的值（即包含自身），只要對代碼稍作修改就好了：

去掉判斷數(shù)組邊界的等號：
target >= array[high]改為 target > array[high]
在與中間值的比較中加上等號：
array[mid] > target改為array[mid] >= target

用二分查找法找尋區(qū)域

之前我們使用二分查找法時，都是基于數(shù)組中的元素各不相同。假如存在重復數(shù)據(jù)，而數(shù)組依然有序，那么我們還是可以用二分查找法判別目標數(shù)是否存在。不過，返回的index就只能是隨機的重復數(shù)據(jù)中的某一個。

此時，我們會希望知道有多少個目標數(shù)存在。或者說我們希望數(shù)組的區(qū)域。
結(jié)合前面的界限查找，我們只要找到目標數(shù)的嚴格上屆和嚴格下屆，那么界限之間（不包括界限）的數(shù)據(jù)就是目標數(shù)的區(qū)域了。

//return type: pair
//the fisrt value indicate the begining of range,
//the second value indicate the end of range.
//If target is not find, (-1,-1) will be returned
pair SearchRange(int A[], int n, int target) 
{
    pair r(-1, -1);
    if (n <= 0) return r;
    
    int lower = BSearchLowerBound(A, 0, n-1, target);
    lower = lower + 1; //move to next element
    
    if(A[lower] == target)
        r.first = lower;
    else //target is not in the array
        return r;
    
    int upper = BSearchUpperBound(A, 0, n-1, target);
    upper = upper < 0? (n-1):(upper - 1); //move to previous element
    
    //since in previous search we had check whether the target is
    //in the array or not, we do not need to check it here again
    r.second = upper;
    
    return r;
}

它的時間復雜度是兩次二分查找所用時間的和，也就是O(log n) + O(log n)，最后還是O(log n)。