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

題目描述

給定一個有序的數組，查找某個數是否在數組中，請編程實現。

分析與解法

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

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

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

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

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

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

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

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

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

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

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

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來解遞歸，所以二分查找法也可以不用遞歸實現，而且它的非遞歸實現甚至可以不用棧，因為二分的遞歸其實是尾遞歸，它不關心遞歸前的所有信息。

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

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

舉例來說：
給予數組和目標數
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;
}

與精確查找不同之處在于，精確查找分成三類：大于，小于，等于（目標數）。而界限查找則分成了兩類：大于和不大于。
如果當前找到的數大于目標數時，它可能就是我們要找的數，所以需要保留這個索引，也因此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時就會形成死循環。因為low無法往上爬超過high。
這兩個實現都是找嚴格界限，也就是要大于或者小于。如果要找松散界限，也就是找到大于等于或者小于等于的值（即包含自身），只要對代碼稍作修改就好了：

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

用二分查找法找尋區域

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

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

//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)。