526互联

二分法及其变体问题

发布时间 2023-09-03 20:51:44作者: 何书文

描述

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

示例 1:

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

示例 2:

输入: nums = [-1,0,3,5,9,12], target = 2
输出: -1
解释: 2 不存在 nums 中因此返回 -1

情况 一

前提：数组有序（升序）、数组中无重复元素

力扣 ?

  • 区间定义：

所处理区间的定义是不变量，在二分查找每次处理边界的时候，需要保持一致，也就是 循环不变量。

写二分法，区间的定义一般有两种：[left, right]，[left, right)

第一种写法

代码如下：

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int left = 0;
        int right = nums.size() - 1;    //  区间形式为 [left, right]
        while(left <= right){
            int middle = left + ((right - left) >> 1);  // 防止溢出，等同 (left + right)/2
            if(nums[middle] > target){
                right = middle - 1; // target 在区间的左半部分
            }else if(nums[middle] < target){
                left = middle + 1;  // target 在区间右半部分
            }else{
                return middle;  //  数组中找到 target 所在的位置
            }
        }
        return -1;  // 未找到 target
    }
};

根据以上代码，分析如下：

区间定义采用 [left, right] 形式，所以有：

  • 循环的条件为：left <= right；left == right 时成立，如：[1, 1] 这个区间；
  • nums[middle] 与 target 不相等时的情况：需要改变区间的左边界或右边界，即：left = middle + 1 或 right = middle - 1；解释：因为 nums[middle] 与 target 已确定不相等，而区间的形式是 [left, right]，所以在下次更新 left 或者 right 时，不再需要包含 nums[middle].

第二种写法

代码如下：

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int left = 0;
        int right = nums.size();    //  区间形式为 [left, right)
        while(left < right){
            int middle = left + ((right - left) >> 1);  // 防止溢出，等同 (left + right)/2
            if(nums[middle] > target){
                right = middle; // target 在区间的左半部分
            }else if(nums[middle] < target){
                left = middle + 1;  // target 在区间右半部分
            }else{
                return middle;  //  数组中找到 target 所在的位置
            }
        }
        return -1;  // 未找到 target
    }
};

根据以上代码，分析如下：

区间定义采用 [left, right) 形式，所以有：

  • 循环的条件为：left < right；与第一种写法相比，left == right 时不成立，如：[1, 1) 这个区间，左右边界相互矛盾；
  • nums[middle] != target 时：需要改变区间的左边界或右边界，与第一种写法相比，区间左边界形式相同，left = middle + 1，而此时，数组中不再包含右边界元素，所以 right = middle；

复杂度分析：

  • 时间复杂度：O(log n)
  • 空间复杂度：O(1)

情况 二：查找第一个值 等于 target 的元素

前提：数组有序（升序）、数组中存在重复的数据；

输入: nums = [1,3,4,5,6,8,8,8,11,18], target = 8
输出: 5
解释: 8 出现在 nums 中并且下标为 5

代码如下：

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int left = 0;
        int right = nums.size() - 1;    //  区间形式为 [left, right]
        while(left <= right){
            int middle = left + ((right - left) >> 1);

            if(nums[middle] > target){
                right = middle - 1;
            }else if(nums[middle] < target){
                left = middle + 1;
            }else{
                if(middle == 0) || (nums[middle - 1] != target)    return middle;
                else    right = middle - 1;
            }
        }
        return -1;
    }
};

根据以上代码，分析如下：

区间定义采用 [left,right] 形式，所以有：

  • 循环条件和 nums[middle] != target 时的边界处理与情况一的对应部分一致；
  • 当 nums[middle] == target 时，因为需要查找第一个值等于 target 的元素，所以再进行判断，确定其是否是第一个符合要求的元素；当 middle == 0 时，是 nums 数组的第一个元素，当然也就是 target 的位置；当 middle 的上一个元素 nums[middle - 1] != target 时，该元素前没有值等于 target 的元素，此时也符合要求；否则需要再进行判断。

按照以上的思想，可以对代码再进行精简，如下：

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int left = 0;
        int right = nums.size() - 1;    //  区间形式为 [left, right]
        while(left <= right){
            int middle = left + ((right - left) >> 1);
            if(nums[middle] >= target){
                right = middle - 1;
            }else if(nums[middle] < target){
                left = middle + 1;
            }
        }

        if(left < nums.size() && nums[left] == target)     return left;
        else return -1;
    }
};

情况 三：查找最后一个值等于给定值的元素

前提：数组有序（升序）、数组中存在重复的数据；

思路与情况 二一致

代码如下：

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int left = 0;
        int right = nums.size() - 1;    //  区间形式为 [left, right]
        while(left <= right){
            int middle = left + ((right - left) >> 1);

            if(nums[middle] > target){
                right = middle - 1;
            }else if(nums[middle] < target){
                left = middle + 1;
            }else{
                if(middle == nums.size() -1) || (nums[middle + 1] != target)    return middle;
                else    left = middle + 1;
            }
        }
        return -1;
    }
};

情况 四：查找第一个大于等于给定值的元素

代码如下：

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int left = 0;
        int right = nums.size() - 1;    //  区间形式为 [left, right]
        while(left <= right){
            int middle = left + ((right - left) >> 1);

            if(nums[middle] >= target){
                if((middle == 0) || (nums[middle - 1] < target))   return middle;
                else    right = middle - 1;
            }else{
                left = middle + 1;
            }
        }
        return -1;
    }
};

情况 五：查找最后一个小于等于给定值的元素

代码如下：

class Solution{
public:
    int search(vector<int>& nums, int target){

        int left = 0;
        int right = nums.size() - 1;

        while(left <= right){
            int middle = left + ((right - left) >> 1);
            if(nums[middle] <= target){
                if(middle == nums.size() || nums[middle + 1] > target)  return middle;
                else    left = middle + 1;
            }else{
                right = middle - 1;
            }
        }
        return -1;
    }
};