二分查找模板总结

三种二分查找场景：

• 寻找一个数
• 寻找左侧边界
• 寻找右侧边界

零、二分查找框架

l 为左侧边界，r 为右侧边界，nums为查找范围，target 为目标数。

具体细节再根据需要更改。

int binarySearch(vector<int>& nums, int target) {
    ...
    int l = 0, r = ...;
    while(...) {
        int m = l + (r - l) / 2;
        if(nums[m] == target) {
            ...
        }
        else if(nums[m] > target) {
            r = ...
        }
        else l = ...
    }
    return ...
}

一、寻找一个数

704. 二分查找

给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。

输入: nums = [-1,0,3,5,9,12], target = 9
输出: 4
解释: 9 出现在 nums 中并且下标为 4

class Solution {
public:
    int binarySearch(vector<int>& nums, int target) {
        int n = nums.size();
        if(n == 1) return nums[0] == target ? 0 : -1;
        int l = 0, r = n - 1;
        while(l <= r) {
            int m = l + (r - l) / 2;
            if(nums[m] == target) {
                return m;
            }
            else if(nums[m] > target) {
                r = m - 1;
            }
            else l = m + 1;
        }
        return -1;
    }
};

二、寻找左侧边界

与上面题目不同的是，升序数组中存在重复的元素，我们需要返回target第一次出现的位置，若没有则返回-1。

输入: nums = [1,2,3,3,3,6,7], target = 3
输出: 2
解释: 3 第一次出现在 nums 中的下标为 2

class Solution {
public:
    int leftBound(vector<int>& nums, int target) {
        int n = nums.size();
        if(n == 1) return nums[0] == target ? 0 : -1;
        int l = 0, r = n - 1; // r = n - 1
        while(l <= r) { // ！l <= r
            int m = l + (r - l) / 2;
            if(nums[m] == target) {
                r = m - 1;// 锁定左边界，收紧右边界
            }
            else if(nums[m] > target) {
                r = m - 1;
            }
            else l = m + 1;
        }
        // while 中止情况为 l = r + 1
        // 根据 l 判断查找情况
        return l < n && nums[l] == target ? l : -1;
    }
};

三、寻找右侧边界

这次的情况同样是存在重复的元素，我们需要返回target最后出现的位置，若没有则返回-1。

输入: nums = [1,2,3,3,3,6,7], target = 3
输出: 4
解释: 3 最后出现在 nums 中的下标为 4

class Solution {
public:
    int rightBound(vector<int>& nums, int target) {
        int n = nums.size();
        if(n == 1) return nums[0] == target ? 0 : -1;
        int l = 0, r = n - 1; // ! r = n -1
        while(l <= r) { // ！l <= r
            int m = l + (r - l) / 2;
            if(nums[m] == target) {
                l = m + 1; // 锁定右边界，收紧左边界
            }
            else if(nums[m] > target) {
                r = m - 1;
            }
            else l = m + 1;
        }
        // while 中止情况为 l = r + 1
        // 根据 r 判断查找情况
        return r >= 0 && nums[r] == target ? r : -1;
    }
};

四、结语

本文的二分模板基于左闭右闭的搜索区间，即[l, r] ，实际运用中我们也可以采用一般的左闭右开的搜索区间，即[l, r)，我们只需要根据查找情况对对细节部分进行修改：

寻找左侧边界：

// 参考
int left_bound(int[] nums, int target) {
    if (nums.length == 0) return -1;
    int left = 0;
    int right = nums.length; // 注意

    while (left < right) { // 注意
        int mid = (left + right) / 2;
        if (nums[mid] == target) {
            right = mid;
        } else if (nums[mid] < target) {
            left = mid + 1;
        } else if (nums[mid] > target) {
            right = mid; // 注意
        }
    }
    if (left == nums.length) return -1;
    // 类似之前算法的处理方式
    return nums[left] == target ? left : -1;
}

寻找右侧边界：

// 参考
int right_bound(int[] nums, int target) {
    if (nums.length == 0) return -1;
    int left = 0, right = nums.length;

    while (left < right) {
        int mid = (left + right) / 2;
        if (nums[mid] == target) {
            left = mid + 1; // 注意
        } else if (nums[mid] < target) {
            left = mid + 1;
        } else if (nums[mid] > target) {
            right = mid;
        }
    }
    if (left == 0) return -1;
    return nums[left-1] == target ? (left-1) : -1;
}