02 二分查找 边界收缩

二分查找的边界值

​ 二分查找很简单，但是也有它的难点，其难点就在于在判定条件和边界值的选择上，很容易就会导致越界或者死循环的情况。

​ 对于循环的判定条件，如果查找区间是闭区间[left, right]，则判定条件要设为while(left<=right)，该判定条件是在出现left > right的情况下终止循环；如果这种闭区间查找区间下使用while(left < right)作为判定条件，该判定条件是在出现left >= right的情况下终止循环，这种情况就没有查找left == right是对应数组位置上的元素，导致错误的查找结果。如果查找区间是闭区间[left, right)，则判定条件可以设为while(left < right)。

​ 对于边界值，例如有序数组array = [1,2,4,4,4,4,5,6], target = 4，存在目标值有多个的情况，此时我们希望得到上边界目标值的索引，即为 5；或者希望得到下边界目标值的索引，即为 2。这时就不能找到目标值就返回，而是需要继续收紧边界进一步查找边界值。二分查找求左右边界值的基本实现如下：

int lowerBound(vector<int> arr, int target){
    int left = 0;
    int right = arr.size();
    int pos = -1;
    while(left < right){
        int mid = left + (right-left)/2;
        if(target == arr[mid]){
            pos = mid;
            right = mid;
        }
        else if(target < arr[mid]){
            right = mid;
        }
        else if(target > arr[mid]){
            left = mid + 1;
        }
    }
    return pos;
}

int upperBound(vector<int> arr, int target){
    int left = 0;
    int right = arr.size();
    int pos = -1;
    while (left < right)
    {
        int mid = left + (right-left)/2;
        if(target == arr[mid]){
            pos = mid;
            left = mid + 1;
        }
        else if(target < arr[mid]){
            right = mid;
        }
        else if(target > arr[mid]){
            left = mid + 1;
        }
    }
    return pos;
}

34 在排序数组中查找元素的第一个和最后一个位置 (opens new window)

给定一个增序的整数数组和一个值，查找该值第一次和最后一次出现的位置

输入是一个数组和一个值，输出为该值第一次出现的位置和最后一次出现的位置（从 0 开始）；如果不存在该值，则两个返回值都设为-1

输入：nums = [5,7,7,8,8,10], target = 8
输出：[3,4]

解析：

​ 本题希望在存在目标值有多个的情况下，找到上边界或下边界目标值的索引。这时使用二分查找搜索目标值时，就不能找到目标值就返回，而是需要继续收紧边界进一步查找边界值。

​ 对于查找目标值的第一个和最后一个位置两种情况我们采用不同的收缩策略：

• 第一个位置即下边界：在找到目标值之后，我们将二分查找的区间更新为中点的左侧区间继续查找目标值
• 最后一个位置即上边界：在找到目标值之后，我们将二分查找的区间更新为中点的右侧区间继续查找目标值

class Solution {
public:

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

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

    vector<int> searchRange(vector<int>& nums, int target) {
        vector<int> ans(2,-1);
        if(nums.empty()){
            return ans;
        }
        ans[0] = lower_bound(nums,target);
        ans[1] = upper_bound(nums,target);
        return ans;
    }
};

​ 所以本质上边界收缩就是实现 C++ STL 中的 lower_bound(),upper_bound()两个函数

lower_bound(Iterator first, Iterator last,const T& val);
upper_bound(Iterator first, Iterator last,const T& val);

​ 其中 first 和 last 都为正向迭代器，[first, last)用于指定该函数的作用范围；val 用于执行目标值。该函数的返回值是一个正向迭代器，当查找成功时，迭代器指向找到的小于或大于目标值的第一个元素；反之，如果查找失败，迭代器的指向和 last 迭代器相同。

​ 直接调用 STL 中 <algorithm> 的对应方法可以更加简洁的完成

class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        vector<int> ans(2,-1);
        if(nums.empty()){
            return ans;
        }
        ans[0] = std::lower_bound(nums.begin(),nums.end(),target)-nums.begin();
        ans[1] = std::upper_bound(nums.begin(),nums.end(),target)-nums.begin()-1;
        return ans[0]>ans[1]?vector<int>{-1,-1}:ans;
    }
};