二分查找

**
二分查找算法的前置条件是,一个已经排序好的序列(在本篇文章中为了说明问题的方便,假设这个序列是升序排列的),这样在查找所要查找的元素时,首先与序列中间的元素进行比较,如果大于这个元素,就在当前序列的后半部分继续查找,如果小于这个元素,就在当前序列的前半部分继续查找,直到找到相同的元素,或者所查找的序列范围为空为止.

时间复杂度: 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;
}

上面的程序的问题在于：
１．如果序列当中有多个元素相同时，查找的时候不见得每次都会返回第一个元素的位置。
２．每次循环体当中都有三种情况，两次比较，有没有办法减少比较的数量，进一步优化程序。
《编程珠玑》中给出了解决这个问题的算法，如下：

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

    while(low+1 != high)
// 这个循环维持的条件是 low < high &&a[low]<target<a[high],
//所以最后若可以找到目标，则只剩下两个数，并满足a[low]<target<a[high],要查找的数就是high.
    {
        mid = low+((high-low)>>1);
        if(a[mid] < target)
//必须保证a[low]<target<=a[high],所以low=mid.
//若low = mid+1,则可能出现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来记录查找到的元素最后一次出现的位置。
//赋初始值为-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;
}

另外，若要求的是找到大于某个数的第一个数，则可以使用如下方法：

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