**
二分查找算法的前置條件是,一個已經(jīng)排序好的序列(在本篇文章中為了說明問題的方便,假設這個序列是升序排列的),這樣在查找所要查找的元素時,首先與序列中間的元素進行比較,如果大于這個元素,就在當前序列的后半部分繼續(xù)查找,如果小于這個元素,就在當前序列的前半部分繼續(xù)查找,直到找到相同的元素,或者所查找的序列范圍為空為止.

時間復雜度: O(lgN)

int bSearch(int *a,int len,int target)
{
    int low = 0;
    int high = len-1;
    int mid;
//注意此處是low<=high不是low<high
    while(low<=high)
    {
        mid = low+((high-low)>>1);
        if (a[mid] == target)
            return mid;
        else if(a[mid] > target)
            high = mid-1;
        else
            low = mid+1;
    }
    return -1;
}

上面的程序的問題在于：
１．如果序列當中有多個元素相同時，查找的時候不見得每次都會返回第一個元素的位置。
２．每次循環(huán)體當中都有三種情況，兩次比較，有沒有辦法減少比較的數(shù)量，進一步優(yōu)化程序。
《編程珠璣》中給出了解決這個問題的算法，如下：

int bSearch(int *a,int len,int target)
{
    int low = -1;
    int high = len;
    int mid;

    while(low+1 != high)
// 這個循環(huán)維持的條件是 low < high &&a[low]<target<a[high],
//所以最后若可以找到目標，則只剩下兩個數(shù)，并滿足a[low]<target<a[high],要查找的數(shù)就是high.
    {
        mid = low+((high-low)>>1);
        if(a[mid] < target)
//必須保證a[low]<target<=a[high],所以low=mid.
//若low = mid+1,則可能出現(xiàn)a[low] <=target
            low = mid;
        else
            high = mid;
    }
    if(high >= len || a[high] != target)
        high = -1;
    return high;

}

上面的算法不好理解，也可以使用下面這種。

int bSearch(int *a,int len,int target)
{
    int low = 0;
    int high = len-1;
    int mid;
    int last =-1;
//定義一個last來記錄查找到的元素最后一次出現(xiàn)的位置。
//賦初始值為-1,當所要查找的元素不存在時，就能直接返回-1.
    while(low<=high)
    {
        mid = low+((high-low)>>1);
        if (a[mid] < target)
            low = mid+1;
        else if(a[mid] > target)
            high = mid-1;
        else
        {
            last =mid;
            high = mid-1;
        }
    }
    return last;
}

另外，若要求的是找到大于某個數(shù)的第一個數(shù)，則可以使用如下方法：

int bSearch(int *a,int len,int target)
{
    int low = 0;
    int high = len-1;
    int mid;
    int last = -1;
    while(low<=high)
    {
        mid = ((high-low)>>1)+low;
        if (a[mid] > target)
        {
            last = mid;
            high = mid-1;
        }
        else
            low = mid+1;
    }
    return last;
}