一、基本二分法的描述

• 二分搜索（英語：binary search），也稱折半搜索、對數(shù)搜索，是一種在有序數(shù)組中查找某一特定元素的搜索算法。搜索過程從數(shù)組的中間元素開始，如果中間元素正好是要查找的元素，則搜索過程結(jié)束；如果某一特定元素大于或者小于中間元素，則在數(shù)組大于或小于中間元素的那一半中查找，而且跟開始一樣從中間元素開始比較。如果在某一步驟數(shù)組為空，則代表找不到。這種搜索算法每一次比較都使搜索范圍縮小一半。

• 復(fù)雜度分析：最壞情況下，關(guān)鍵詞比較次數(shù)為log2(n+1)，且期望時間復(fù)雜度為O(log2n)；

二、基本二分法的步驟與實現(xiàn)方法

• 二分法的前提：已排好序的數(shù)組A[n], 其中 A[0] <= A[1] <= ... <= A[n],以及一個待查找的值K。
• 步驟：
  ???? 1. 令low = 0， high = n - 1，初始的查找區(qū)域為[low， high].
  ???? 2. 取low和high的中間值mid = (low+high)/2。
  ???? 3. 如果A[mid] = K，則返回mid, 如果不等，則重新確定查找區(qū)間。
  ???? 4. 當(dāng)low > high 時，則表示區(qū)間已經(jīng)失效，如果還未找到，則表示數(shù)組中不包含K的值，返回-1。
• 重新確定查找區(qū)間的規(guī)則：
  ???? 1. 如果A[mid] < K, 則由數(shù)組的有序性可知T應(yīng)該存在于[mid+1, high]之間。
  ???? 2. 同理，如果A[mid] > K, 則T應(yīng)該存在于[low, mid-1]區(qū)間。

• 代碼如下：

template<class T>
int binary_search(vector<T> &A, T K)
{
    int low = 0;
    int high = A.size() - 1;
    
    while( low < high )
    {
        int mid = (low + high)/2;

        if( A[mid]  < K )
            low = mid + 1;
        else if( A[mid] > k )
            high = mid - 1;
        else
            return mid;
    }  

    return -1;      /*返回-1表示數(shù)組不存在K的值*/
 }

三、二分法的變形算法

3.1 求數(shù)組中最大值

• 給定一個數(shù)組A，長度為n，其中A[0] < A[1] ... < A[i] > A[i+1] > ... > A[n-1]，求其中的最大值，返回其下標。

template<class T>
int binary_serach_peek(vector<T> &A)
{
    int low = 0;
    int high = A.size() - 1;
    while( low < high )
    {
        int mid = low + (high - low)/2;
        if( A[mid] > A[mid-1] && A[mid] > A[mid+1])
            return mid;
        else if( A[mid] > A[mid-1] && A[mid] < A[mid+1])
            low = mid;
        else
            high = mid;
    }
    return -1;
}