LeetCode - 二分查找

“90%的程序员不能写出正确的二分查找” – 不是我说的

二分查找及其变种有很多种形式，例如查找第一个出现的、查找出现的区间，等。但都不能脱离一个宗旨：每次查找都要有下标的更迭。

一个经典的二分查找的错误是，出现了下标分别处在了i和i+1，而却判断nums[l] < nums[mid] ? l = mid : r = mid。（这里是不规范的写法）。这会可能导致产生一个死循环，因为，(i + i + 1) // 2 = i。如果第一个判断条件被命中，则永远循环在了那儿。

另外一个不恰当的做法是，判断两边的值，进而判断是否到了边界，然后判断mid值。这种做法可能导致的错误是，l == i, r == i + 1 时，我的mid又要被判断了一次。这种做法是比较冗余的，而且可能导致insidious bug。

基本正确做法是，

bool bin_search(vector<int>& nums, int target) 
/* 判断是否存在，且数值不重复的情况 */
{
    int l = 0, r = nums.size() -1;
    while (l < r) {
        int mid = (l + r) / 2;
        if (nums[mid] < target)
        /* target在 mid左边 */
        {
            l = mid + 1;
        }
        else
        /* 因为 (i + i + 1) // 2 -> i, r = mid就行了 */
        {
            r = mid;
        }
    }
    return nums[l] == target;
}

一些变种：

数值存在，找边界：

/* LeetCode p34 */

class Solution {
   public:
    vector<int> searchRange(vector<int>& nums, int target) {
        if (nums.size() == 0) return vector<int>{-1, -1};
        int l = 0, r = nums.size() - 1, mid;

        int i = l, j = r;

        /* 找小边界 */
        while (j > l) {
            mid = (j + l) / 2;
            if (nums[mid] < target) {
                l = mid + 1;
            } else {
                j = mid;
            }
        }

        /* 不存在，返回 */
        if (nums[j] != target) {
            return vector<int>{-1, -1};
        }

        /* 找大边界 */
        while (i < r) {
            mid = (i + r) / 2;
            if (nums[mid] <= target) {
                i = mid + 1;
            } else {
                r = mid;
            }
        }

        return nums[r] == target ? vector<int>{l, r} : vector<int>{l, r - 1};
    }
};

二分查找的边界条件十分值得注意。很容易出现查找缺漏、死循环的情况。

如有错误，恳请指正！