二分查找板子 – D

二分查找实际上就是采用了分治法的思想

以下模板都以升序数组为准

模板一: 标准的二分查找

场景：数组元素有序且不重复

有的话返回索引，没有返回-1

int binarySearch(vector<int>& arr, int target) {
    int left = 0, right = nums.size() - 1;
    
    while (left <= right) {//<=指可以取到右区间，是[left,right]
        int mid = left + ((right - left) >> 1);
        if (nums[mid] == target) return mid;
        else if (nums[mid] > target) right = mid - 1;//证明target可能在mid左侧
        else left = mid + 1;//证明nums[mid] < target, target可能在mid右侧
    }
    
    return -1;
}

模板二：二分查找找边界

二分查找左/有边界是二分查找的变式，一般有如下场景：

1）第一种情况

• 数组总体有序，包含重复元素
• 数组部分有序，且不包含重复元素

2）第二种情况

• 数组部分有序，且包含重复元素

二分查找找左边界

1）针对第一种情况：

int binarySearch(vector<int>& nums, int target) {
    int left = 0, right = nums.size() - 1;
    
    while (left < right) {//这是左闭右开[,)，不包含最后一个数，left = right 的时候会跳出
        int mid = left + ((right - left) >> 1);
        if (nums[mid] < targrt) left = mid + 1;
        else right = mid;//nums[mid] >= target, 都需要往左边收缩边界（主要）
    }
    //因为里面是没有判断left = right 这个索引的位置，需要打个补丁
    return nums[left] == target ? left : -1;
}

2）针对第二种情况（模板有误）

二分查找找右边界

1）针对第一种情况

int binarySearch(vector<int>& nums, int target) {
	int left = 0, right = nums.size() - 1;
    int mid;
    
    while (left < right) {
        mid = left + ((right - left) >> 1) + 1;//需要注意，这里多加了个1，这样无论是奇偶数，中间位置都偏右，这样避免了死循环（如果不加1，比如{2，2}就会死循环
        if (nums[mid] > target) right = mid - 1;//收缩右边界
        else left = mid;//numd[mid] <= target,都需要收缩左边界（主要）
    }
    //打个补丁,这里写左右都可以
    return nums[left] == target ? left : -1;
}

2)针对第二种情况

二分查找找左右边界

分别查找左右边界即可

1）第一种情况

vector<int> searchRange(vector<int>& nums, int target) {
    vector<int> res{-1,-1};//res[0]存左边界，res[1]存右边界
    
    int left = 0, right = nums.size() - 1;
    int mid;
    
    while (left < right) {//先找左边边界
        mid = left + ((right - left) >> 1);
        if (nums[mid] < target) left  = mid + 1;
        else right = mid;
    }
    res[0] = nums[left] == target ? left : -1;
    
    if (res[0] != -1) {//存在左边边界查找右边边界
        if (left == nums.size() - 1 || nums[left + 1] != target) {//可能只有一个target,它的位置可能在末尾/其他位置
            res[1] = left;
        }
        else {//有多个target
            right = nums.size() - 1;
            
            while (left < right) {
                mid = left + ((right - left) >> 1) + 1;
                if (nums[mid] > target) right = mid - 1;
                else left = mid;
            }
            res[1] = nums[left] == target ? left : -1;
        }
    }
    
    return res;
}

模板三：二分查找找极值点

二分查找的一种变式：找极值，即是v或者^的最值点；

我们查找的时候不再是和target进行比较，而是和相邻元素比较，以达到某种单调区间检测的效果

下面以查找^的极值点写一个模板：

int binarySearch(vector<int>& nums) {
    int left = 0, right = nums.size() - 1;
    int mid;
    
    while (left <= right) {
       mid = left + ((right - left) >> 1);
       
        if (nums[mid] > nums[mid] + 1 && nums[mid] > nums[mid - 1]) return mid;
        else if (nums[mid] > nums[mid + 1]) right = mid - 1;//极值点在左边
        else left = mid + 1;//极值点在右边
    }
    
    return -1;
}