首页 > 专题系列 > 经典问题 > 无处不在的二分查找
2014
03-22

无处不在的二分查找

我们都知道二分查找算法,实际上二分查找以及其扩展应用是很广泛的。这里收集了一些和二分查找有关的有趣问题。强烈建议大家看完问题后最小化浏览器,先尝试自己去解决,然后再看代码,问题都不是太难。

问题1描述

给一个已经排序的数组,其中有N个互不相同的元素。要求使用最小的比较次数找出其中的一个元素。(你认为二分查找在排序数组里找一个元素是最优的算法的吗?)

不需要太多的理论,这是一个典型的二分查找算法。先看下面的代码:

// 返回要查找元素的下标,-1为没有找到
int BinarySearch(int A[], int l, int r, int key)
{
    int m;
    while( l <= r )
    {
        m = l + (r-l)/2;

        if( A[m] == key ) //第一次比较
            return m;

        if( A[m] < key ) // 第二次比较
            l = m + 1;
        else
            r = m - 1;
    }

    return -1;
}

理论上,我们最多需要 logN+1 次比较。仔细观察,我们在每次迭代中使用两次比较,除了最后比较成功的一次。实际应用上,比较也是代价高昂的操作,往往不是简单的数据类型的比较。减少比较的次数也是优化的方向之一。

下面是一个比较次数更少的实现:

// 循环不变式: A[l] <= key &  A[r] > key
// 边界: |r - l| = 1
// 输入: A[l .... r-1]
int BinarySearch(int A[], int l, int r, int key)
{
    int m;
    while( r - l > 1 )
    {
        m = l + (r-l)/2;

        if( A[m] <= key )
            l = m;
        else
            r = m;
    }
    if( A[l] == key )
        return l;
    else
        return -1;
}

在while循环中,我们仅依赖于一次比较。搜索空间( l->r )不断缩小,我们需要一个比较跟踪搜索状态。

需要注意的,要保证我们恒等式(A[l] <= key & A[r] > key)正确,后面还会用到循环不变式。

大家可以在这个链接看到上面代码的测试:http://ideone.com/76bad0

问题2描述

给一个有N个互不相同的元素的已排序数组,返回小于或等于给定key的最大元素。 例如输入为 A = {-1, 2, 3, 5, 6, 8, 9, 10}   key = 7,应该返回6.

分析:

我们可以用上面的优化方案,还是保持一个恒等式,然后移动 左右两个指针。最终 left指针会指向 小于或等于给定key的最大元素(根据恒等式A[l] <= key and A[r] > key)。

- > 如果数组中所有元素都小于key,左边的指针left 会一直移动到最后一个元素。

- > 如果数组中所有元素都大于key,这是一个错误条件,无答案。

- > 如果数组中的所有元素都 <= key,这是最坏的情况根据下面的实现

代码:

// 循环不变式: A[l] <= key and A[r] > key
// 边界条件: |r - l| = 1
// 输入: A[l .... r-1]
// 先决条件: A[l] <= key <= A[r]
int Floor(int A[], int l, int r, int key)
{
    int m;
    while( r - l > 1 )
    {
        m = l + (r - l)/2;
        if( A[m] <= key )
            l = m;
        else
            r = m;
    }
    return A[l];
}

// 初始调用
int Floor(int A[], int size, int key)
{
    // 如果 key < A[0] 不符合条件
    if( key < A[0] )
        return -1;

    return Floor(A, 0, size, key);
}

在这个链接可以看到相应的测试: http://ideone.com/z0Kx4a.

这个函数在C++的STL里面有实现 :  lower_bound 函数

问题3描述

给一个有重复元素的已排序数组,找出给定的元素key出现的次数,时间复杂度要求为logN.

分析

其实可以对上面的程序稍作修改,思路就是分别找出key 第一次出现的位置和最后一次出现的位置。

// 输入: 数组区间 [l ... r)
// 循环不变式: A[l] <= key and A[r] > key
int GetRightPosition(int A[], int l, int r, int key)
{
    int m;
    while( r - l > 1 )
    {
        m = l + (r - l)/2;
        if( A[m] <= key )
            l = m;
        else
            r = m;
    }
    return l;
}

// 输入: 数组区间 (l ... r]
// 恒等式: A[r] >= key and A[l] > key
int GetLeftPosition(int A[], int l, int r, int key)
{
    int m;
    while( r - l > 1 )
    {
        m = l + (r - l)/2;
        if( A[m] >= key )
            r = m;
        else
            l = m;
    }
    return r;
}

int CountOccurances(int A[], int size, int key)
{
    // 找出边界
    int left = GetLeftPosition(A, -1, size-1, key);
    int right = GetRightPosition(A, 0, size, key);

    // key有可能不存在,需要判断
    return (A[left] == key && key == A[right])?
           (right - left + 1) : 0;
}

测试程序:http://ideone.com/zn6R6a.

问题4描述

有一个已排序的数组(无相同元素)在未知的位置进行了旋转操作,找出在新数组中的最小元素所在的位置。

例如:原数组 {1,2,3,4,5,6,7,8,9,10}, 旋转后的数组可能是 {6,7,8,9,10, 1,2,3,4,5 },也可能是 {8,9,10,1,2,3,4,5,6,7 }

分析:

我们不断的缩小 l 左指针和 r 右指针直到有一个元素。把上面划横线的作为第一部分,剩下的为第二部分。如果中间位置m落在第一部分,即A[m] < A[r] 不成立,我们排序掉区间 A[m+1 ... r]。 如果中间位置m落在第二部分,即 A[m]<A[r]成立,我们缩小区间至 A[m+1 .... r ]。 直到搜索的区间大小为1就结束。

int BinarySearchIndexOfMinimumRotatedArray(int A[], int l, int r)
{
    int m;

    // 先决条件: A[l] > A[r]
    if( A[l] <= A[r] )
        return l;

    while( l <= r )
    {
        //终止条件
        if( l == r )
            return l;

        m = l + (r-l)/2; // 'm' 可以落在第一部分或第二部分

        if( A[m] < A[r] )
            // (m < i <= r),可以排除 A[m+1 ... r]
            r = m;
        else
            // min肯定在区间 (m < i <= r),
            // 缩小区间至 A[m+1 ... r]
            l = m+1;
    }
    return -1;
}

int BinarySearchIndexOfMinimumRotatedArray(int A[], int size)
{
    return BinarySearchIndexOfMinimumRotatedArray(A, 0, size-1);
}

测试程序:http://ideone.com/KbwDrk.

后续文章中讲继续使用二叉搜索来解决几个有趣的问题,欢迎大家的评论

ACM之家原创,链接:http://www.acmerblog.com/ubiquitous-binary-search-5345.html


  1. Good task for the group. Hold it up for every yeara??s winner. This is a excellent oppotunity for a lot more enhancement. Indeed, obtaining far better and much better is constantly the crucial. Just like my pal suggests on the truth about ab muscles, he just keeps obtaining much better.

  2. 问题3中,GetRightPosition()和GetLeftPosition()与STL中的upper_bound()和lower_boune()的代码实现一样吗?