二分查找

不同条件下二分查找边界问题

作者 Trevor Cui 日期 2018-01-27
basis
二分查找

二分查找问题总的来说不复杂，主要麻烦的点在于边界问题。且不同的条件下二分的写法也都不一样。接下来就做一个总结。

最基础的二分查找

先看最基础，写起来也最简单的二分查找：只需要找到相等的位置就返回。

int binarySearch(vector<int>& nums, int k) {
    int left = 0, right = nums.size() - 1;
    while(left <= right) {
        int mid = (left + right) / 2;
        if(nums[mid] < k) left = mid + 1;
        else if(nums[mid] > k) right = mid - 1;
        else return mid;
    }
    return -1;
}

四个不同的边界问题

接下来的变种问题都对于单调不递减数组而言。

查找最后一个等于或者小于 key 的元素

int lastEqualSmaller(vector<int>& nums, int k) {
    int left = 0, right = nums.size() - 1;
    while(left <= right) {
        int mid = (left + right) / 2;
        if(nums[mid] > k) right = mid - 1;
        else left = mid + 1;
    }
    return right;
}

查找最后一个小于 key 的元素

int lastSmaller(vector<int>& nums, int k) {
    int left = 0, right = nums.size() - 1;
    while(left <= right) {
        int mid = (left + right) / 2;
        if(nums[mid] >= k) right = mid - 1;
        else left = mid + 1;
    }
    return right;
}

查找第一个等于或者大于 key 的元素

int firstEqualLarger(vector<int>& nums, int k) {
    int left = 0, right = nums.size() - 1;
    while(left <= right) {
        int mid = (left + right) / 2;
        if(nums[mid] >= k) right = mid - 1;
        else left = mid + 1;
    }
    return left;
}

查找第一个大于 key 的元素

int firstLarger(vector<int>& nums, int k) {
    int left = 0, right = nums.size() - 1;
    while(left <= right) {
        int mid = (left + right) / 2;
        if(nums[mid] > k) right = mid - 1;
        else left = mid + 1;
    }
    return left;
}

总结

二分查找变种较多，不过它们的“套路”是一样的，以上代码就是其套路，如何快速写出二分查找的代码，只需按照以下步骤即可：

首先判断出是返回 left，还是返回 right

因为我们知道最后跳出 while (left <= right) 循环条件是 right < left，且 right = left - 1。最后 right 和 left 一定是卡在“边界值”的左右两边，如果是比较值为 key，查找小于等于（或者是小于）key 的元素，则边界值就是等于 key 的所有元素的最左边那个，其实应该返回 left。

判断出比较符号

也就是 if (array[mid] ? key) 中的判断符号，结合步骤 1 和给出的条件，如果是查找小于等于 key 的元素，则知道应该使用判断符号 >=，因为是要返回 left，所以如果 array[mid] 等于或者大于 key，就应该使用 >=。

FEATURED TAGS
basis