二分查找的几种情形 | TWO2TWO2TWO2TWO2

二分查找是一个很基础的算法，但是它的边界条件值得注意。

int binary_search(vector<int>& nums, int low, int high, int target) {
    int mid;
    while (low <= high) {
        mid = (low + high) >> 1;
        if (nums[mid] == target) return mid;
        else if (nums[mid] < target) low = mid + 1;
        else high = mid - 1;
    }
    return -1;
}

这个是最原始的二分查找版本。在发现一个nums[mid] == target后，立即返回；如果nums中不存在target，则返回-1。假如nums中存在多个target，则返回的target所处位置不确定。程序的思路如下（记end = nums.size())：

循环的每一轮，都在使范围[low, high]缩减。
如果nums中所有数都大于/小于target，那么在范围大小缩减为负数后，循环停止，返回-1。
如果nums中存在target：在循环过程中，程序保证nums[low] <= target <= nums[high]。这意味着，对于num in nums[0, low)，都有num < target；对于num in nums[high + 1, end)，都有num > target。因此，如果nums[mid] < target，说明nums[0, mid]里面不存在target，需要令low = mid + 1。high同理，如果nums[mid] > target，说明nums[mid, end)中不存在target，需要令high = mid - 1。范围[low, high]持续在缩减，mid总在[low, high]中取，所以总有一轮会有nums[mid] == target。
如果nums[0] < target < nums.back()但是nums中不存在target：程序在保证nums[low] <= target <= nums[high]的同时不断缩减[low, high]。由于nums[mid]不可能等于target，所以程序会在low > high之后结束循环返回-1。

这个版本的二分查找虽然简单，但是功能不够强大。现在我们要为二分查找增加一个新的功能：在nums中不存在target时返回大于target的最小数的下标。

int binary_search(vector<int>& nums, int low, int high, int target) {
    int mid;
    while (low <= high) {
        mid = (low + high) >> 1;
        if (nums[mid] == target) return mid;
        else if (nums[mid] < target) low = mid + 1;
        else high = mid - 1;
    }
    return low;
}

这个版本和上一个版本仅有返回值的区别，返回值low指向nums中最小的比target大的数（如果这个数存在）。依旧分情况讨论：

如果nums中所有数都大于target，那么范围会持续以high = mid - 1的方式缩减。最终，low == 0, high == -1。nums[low]是nums中最小的数，因此也是nums中最小的比target大的数。
如果nums中所有数都小于target，那么范围会持续以low = mid + 1的方式缩减。最终，low == end, high == end - 1。low并不指向nums中的数，这也说明了nums中不存在比target大的数。
如果nums中存在target，情况和上个版本分析的一样。
如果nums[0] < target < nums.back()但是nums中不存在target：程序保证nums[low] <= target <= nums[high]，同时也保证对于num in nums[0, low)，有num < target；对于num in nums[high+1, end)，有num > target。在循环结束的时候，有low = high + 1。由于low in [high+1, end)，所以也有nums[low] > target。结合nums是有序的这一点，可以知道nums[low]是nums中最小的比target大的数。同理，nums[high]是nums中最大的比target小的数。

前面有提到，当nums中存在多个target时，返回的target是第几个是不确定的。那么是否可以让二分查找程序返回指定的target下标呢？答案是可以的。下面这个版本的二分查找，固定返回第一个target的下标：

int binary_search(vector<int>& nums, int low, int high, int target) {
    int mid;
    while (low < high) {
        mid = (low + high) >> 1;
        if (nums[mid] < target) low = mid + 1;
        else high = mid;
    }
    return low;
}

这个版本的二分查找和上面的很相似，区别是在nums[mid] == target时，令high = mid，而不直接返回mid。这样能够保证，对于num in nums[0, low)，有num < target；对于num in nums[high, end)，有num >= target。程序只有在low == high时才会结束循环。在结束时，low确定了一个边界：在它左边的数都小于target，在它右边（包括它）的数都不小于target。如果nums中存在多个target，那么low指向的就会是第一个target。

如果在nums中不存在target时，由于上面描述的low作为边界的特性，可以知道：nums[low]是nums中最小的大于target的数。显然,nums[low-1]也是nums中最大的小于target的数。这和上一个版本的返回值很像，但是有一个区别：在nums中所有数都小于target时，返回的会是end - 1而非end。这是循环判断条件为low < high而非low <= high导致的。这个瑕疵无法避免，因为若判断条件是low <= high，在nums中所有数都大于target时程序会陷入死循环。

下面代码是上面的对称版，返回最后一个target的下标：

int binary_search(vector<int>& nums, int low, int high, int target) {
    int mid;
    while (low < high) {
        mid = ((low + high) >> 1) + 1;
        if (nums[mid] > target) high = mid - 1;
        else low = mid;
    }
    return high;
}

由于是对称，mid应该向上取整。这里并不是严格意义的向上取整，但是只要让mid不超出[low, high]范围即可。其他的和上面的没有本质区别，不再赘述。

Share on: