LeetCode算法笔记-三道简单题题帮18万人探索二分查找区间的开与闭

大家好，我是给自己写知识笔记都要做标题党，精通标题党技巧，却依然骗不到评论关注的假讲师。

704题：（题目描述、示例、提示在此不再给出。）

先读题，数组是升序数组，且数组中的所有元素都不重复。我们不用担心二分查找的目标元素不唯一的问题。这都是使用二分法的条件。

二分查找的边界条件比较多，所及即使二分法逻辑比较简单，也总是“一写就废”。主要因为我们容易对区间的定义混淆。

左闭右闭区间和左闭右开区间的两种解法都是对于寻找一个数字的基本的二分搜索，只有区间选择的区别：

在这里插入图片描述

左闭右闭区间：

class Solution {
    public int search(int[] nums, int target) {
        //定义target在左闭右闭的区间里，[left, right]
        int left = 0, right = nums.length - 1;
        
        // left==right，区间[left, right]有效，用 <=
        while (left <= right) {
            // 防止溢出,此题等价(left + right)/2
            int mid = left + ((right - left) >> 1);
            if (nums[mid] == target)
                // 找到目标值，返回下标
                return mid;
            else if (nums[mid] < target)
                // target 在右区间，所以[middle + 1, right]
                left = mid + 1;
            else if (nums[mid] > target)
                // target 在左区间，所以[left, middle - 1]
                right = mid - 1;
        }
        // 未找到目标值
        return -1;
    }
}

在这里插入图片描述

左闭右开区间：

class Solution {
    public int search(int[] nums, int target) {
        // 定义target在左闭右开的区间里，[left, right)  
        int left = 0, right = nums.length;
        
        // 因为left == right的时候，在[left, right)是无效的空间，用 <
        while (left < right) {
            int mid = left + ((right - left) >> 1);
            if (nums[mid] == target)
                // 数组中找到目标值，直接返回下标
                return mid;
            else if (nums[mid] < target)
                // target 在右区间，[middle + 1, right)
                left = mid + 1; 
            else if (nums[mid] > target)
                // target 在左区间，[left, middle)
                right = mid;
        }
        // 未找到目标值
        return -1;
    }
}

避免当 target 小于nums[0] nums[nums.length - 1]时多次循环运算。我们可以在函数体内加上如下代码提高效率，这些小细节在项目开发中挺重要的：
在这里插入图片描述

if (target < nums[0] || target > nums[nums.length - 1])
{
	return -1;
}

278题：

1 <= bad <= n <= 2^31 - 1

提示数字很大，我们要忍一下。

依然是简单的二分法，但是数组越界处理方面有一点点小细节：
在这里插入图片描述

int mid = left + ((right - left)>>1);
//位运算更快，以及在基础数字较大时，left+(right - left)/2 比起（right + left）/ 2，更不容易越界

public class Solution extends VersionControl {
    public int firstBadVersion(int n) {
        int left = 0;
        int right = n-1;

        while(left <= right){
            int mid = left + ((right - left)>>1);//这里
            //是否为错误版本，若是：
            if(isBadVersion(mid)){
                //缩圈，找更靠前的，mid本身就是错误版本，不用管它，所以是mid-1。
                right = mid -1;
            //若不是：
            }else{
                //缩圈，找更靠后的，mid本身就是错误版本，不用管它，所以是mid+1。
                left = mid +1;
            }
        }
        return left;
    }
}

35题

本题的思路也没有很大的变化，依然是基本二分。但是对于返回值有要求有点变化。

如果找到匹配的元素，返回元素下标，即mid；此步骤没变
如果没有找到，则要返回能插入的元素下标，此处是重点。

这种情况根据我们的区间选择不同，返回值也正好相反。
在这里插入图片描述

我们只看mid，如果在左闭右闭区间内，返回值应该是mid+1；如果在左闭右开区间内，返回值应该是mid。

但是mid是在while循环中定义的变量，无法在while外return。

那我们就要找和上面结论相等的值：左闭右闭区间内：mid + 1 == left == right +2；左闭右开区间内：mid == right + 1 == left - 1

找到本质联系之后，本题就迎刃而解了：

class Solution {
    public int searchInsert(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;

        while(left <= right){
            int mid = left + ((right - left) >> 2);

            if(nums[mid] == target)
                return mid;
            else if(nums[mid] > target)
                right = mid - 1;
            else if(nums[mid] < target)
                left = mid + 1;
        }
        //我们选的是左闭右闭区间，此处return应为left，
        return left;
    }
}