数据结构算法题之二分查找算法

相信大家都知道二分查找的基本算法，如下所示，这就是二分查找算法代码：

int binarySearch(int a[], int n, int t)
{
    int l = 0, u = n - 1;
    while (l <= u) {
        int m = l + (u - l) / 2; // 同（l+u）/ 2，这里是为了防溢出
        if (t > a[m])
            l = m + 1;
        else if (t < a[m])
            u = m - 1;
        else
            return m;
    }
    return -(l+1);
}

算法的思想就是：从数组中间开始，每次排除一半的数据，时间复杂度为O(lgN)。这依赖于数组有序这个性质。如果t存在数组中，则返回t在数组的位置；否则，不存在则返回-(l+1)。

这里需要解释下为什么t不存在数组中时不是返回-1而要返回-(l+1)。首先我们可以观察 l 的值，如果查找不成功，则 l 的值恰好是 t 应该在数组中插入的位置。

举个例子，假定有序数组a={1, 3, 4, 7, 8}， 那么如果t=0，则显然t不在数组中，则二分查找算法最终会使得l=0 > u=-1退出循环；如果t=9，则t也不在数组中，则最后l=5 > u=4退出循环。如果t=5，则最后l=3 > u=2退出循环。

因此在一些算法中，比如DHT（一致性哈希）中，就需要这个返回值来使得新加入的节点可以插入到合适的位置中，在求最长递增子序列的NlgN算法中，也用到了这一点，参见:

http://blog.csdn.net/ssjhust123/article/details/7798737

还有一个小点就是之所以返回-(l+1)而不是直接返回 -l 是因为 l 可能为0，如果直接返回 -l 就无法判断是正常返回位置0还是查找不成功返回的0。

现在考虑一个稍微复杂点的问题，如果有序数组中有重复数字，比如数组a={1, 2, 3, 3, 5, 7, 8}，需要在其中找出3第一次出现的位置。这里3第一次出现位置为2。这个问题在《编程珠玑》第九章有很好的分析，这里就直接用了。

算法的精髓在于循环不变式的巧妙设计，代码如下：

int binarySearchFirst(int a[], int n, int t)
{
    int l = -1, u = n;
    while (l + 1 != u) {
        
        int m = l + (u - l) / 2; //同（l+u）/ 2
        if (t > a[m])
            l = m;
        else
            u = m;
    }
    
    int p = u;
    if (p>=n || a[p]!=t)
        p = -1;
    return p;
}

算法分析：设定两个不存在的元素a[-1]和a[n]，使得a[-1] < t <= a[n]，但是我们并不会去访问这两个元素，因为(l+u)/2 > l=-1, (l+u)/2 < u=n。循环不变式为la[l] && t<=a[u] 。循环退出时必然有l+1=u, 而且a[l] < t <= a[u]。

循环退出后u的值为t可能出现的位置，其范围为[0, n]，如果t在数组中，则第一个出现的位置p=u，如果不在，则设置p=-1返回。该算法的效率虽然解决了更为复杂的问题，但是其效率比初始版本的二分查找还要高，因为它在每次循环中只需要比较一次，前一程序则通常需要比较两次。

举个例子：对于数组a={1, 2, 3, 3, 5, 7, 8}，我们如果查找t=3，则可以得到p=u=2，如果查找t=4，a[3]=n, 比如t=9，则u=7，此时也是设置p=-1.特别注意的是，l=-1，u=n这两个值不能写成l=0，u=n-1。虽然这两个值不会访问到，但是如果改成后面的那样，就会导致二分查找失败，那样就访问不到第一个数字。如在a={1，2，3，4，5}中查找1，如果初始设置l=0，u=n-1，则会导致查找失败。

int binarySearchLast(int a[], int n, int t)
{
    int l = -1, u = n;
    while (l + 1 != u) {
        
        int m = l + (u - l) / 2;
        if (t >= a[m])
            l = m;
        else
            u = m;
    }
    
    int p = l;
    if (p<=-1 || a[p]!=t)
        p = -1;
    return p;
}

int binarySearchFirstAndLast(int a[], int n, int t, int firstFlag)
{
    int l = 0;
    int u = n - 1;
    while(l <= u) {
        int m = l + (u - l) / 2;
        if(a[m] == t) { //找到了，判断是第一次出现还是最后一次出现
            if(firstFlag) { //查询第一次出现的位置
                if(m != 0 && a[m-1] != t)
                    return m;
                else if(m == 0)
                    return 0;
                else
                    u = m - 1;
            } else {   //查询最后一次出现的位置
                if(m != n-1 && a[m+1] != t)
                    return m;
                else if(m == n-1)
                    return n-1;
                else
                    l = m + 1;
            }
        }
        else if(a[m] < t)
            l = m + 1;
        else
            u = m - 1;
    }

    return -1;
}