二分查找的代码分析

本文对标准实现的二分查找进行了正确性分析。

标准实现的二分查找，如果依据STL实现，那最核心的就是lower_bound函数，具体地，实现如下（仅贴出默认比较函数）：

template<class ForwardIt, class T>
bool binary_search(ForwardIt first, ForwardIt last, const T& value)
{
    first = std::lower_bound(first, last, value);
    return (!(first == last) && !(value < *first));
}

template<class ForwardIt, class T>
ForwardIt lower_bound(ForwardIt first, ForwardIt last, const T& value)
{
    ForwardIt it;
    typename std::iterator_traits<ForwardIt>::difference_type count, step;
    count = std::distance(first, last);
 
    while (count > 0) {
        it = first; 
        step = count / 2; 
        std::advance(it, step);
        if (*it < value) {
            first = ++it; 
            count -= step + 1; 
        }
        else
            count = step;
    }
    return first;
}

上述代码见std::lower_bound.

把上述迭代器版本转换为通常使用的low-high版本，同时使用直观的比较符号(将!(value < *first) 变为 value == *first)，并去掉模板，就是如下代码(使用vector作为输入容器)：

bool binary_search(const vector<int> &sorted_arr, int target)
{
    int index = lower_bound(sorted_arr, target);
    return (index != sorted_arr.size() && sorted_arr[index] == target);
}

int lower_bound(const vector<int> &sorted_arr, int target)
{
    int low = 0,
        high = sorted_arr.size() - 1;
    while(low <= high)
    {
        int mid = low + (high - low)/2;
        if(sorted_arr[mid] < target){ low = mid + 1; }
        else{ high = mid - 1; }
    }
    return low;
}

我们对上述代码做一下分析：

首先这是一个非常激进的代码，一眼看过去并不好说它是对的。原因主要是：

如果 sorted_arr[mid] == target , 那么high会直接跳过期望值mid，而变为mid-1，这还能得到正确结果吗？

答案是——是正确结果。原因是因为循环保持条件时low <= high,其中的=至关重要。因为这将要求循环退出时low = high + 1!

回到刚刚的假设，即sorted_arr[mid] == target, 我们将会设置high = mid-1, 可想而知，在排序的数组中，现在high指向的元素必然小于等于target（如果有重复，则可能是=）.我们先不考虑重复的情况，即high指向的元素小于target。那么也必然有mid指向的元素将始终小于target。这样low就不断通过low = mid + 1来向high靠拢，则必然有low == high，然后mid == low, 依然进入<的分支，即low = mid + 1, 然后循环结束——最终low还是指向了sorted_arr[mid] == target的位置，即high + 1. 如果考虑重复，则只要mid的值等于target，那么必然high要向mid左边移动，故必然high会指向所有重复target的左边。这时又变为上没有重复的情况。

再稍微考虑下array中无target的情况：在循环退出的前一刻，必然有low == mid(low与high隔1个或0个元素)

要么由分支<退出，首先必然有退出前low == high == mid(因为mid+1后就大于high了，如果low与high隔1个元素，那么mid+1后只能等于high，不会退出)。此时因为mid值小于<,则low向右移动后，保证了比mid指向的值大。如果之前high向左移动过，即high最后一次左移，必然有sorted_arr[mid'] >= target（这里只能大于），然后high变为mid-1, 现在low = mid + 1 = high + 1, 即指向的元素大于target，且是第一个大于target的位置。当然也可能high从来没有左移过，那么low此时就越界成为尾后位置了。这也是我们在binary_search中首先判断返回的位置是否是尾后的原因。
要么由else分支(>=)退出。因为退出时改变的是high的值，故low值不变——而low == mid, 且进入此分支的条件是sorted_arr[mid] >= target, 故low指向的元素大于（这里没有等）target。由二分查找的过程可以保证是第一个大于target的值——如果不是，也就是说mid前面还有比target大的数，而low ==mid, 即low指针指向的值的前面还有比target大的数，这与low指针的移动规则相悖，不成立，故其是第一个大于target的数。