[数据结构与算法] 一文讲清楚二分查找细节

开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> 数据结构与算法 -> 一文讲清楚二分查找细节 -> 正文阅读

[数据结构与算法]一文讲清楚二分查找细节

1、二分查找题型要求

带查找的数组有序或者部分有序
要求查找时间复杂度 $l o g (n)$

2、二分查找关键三问

left<right 还是 left<=right ?
mid = left + (right-left)/2 还是 mid =left + (right-left)/2+1
left=mid 还是 left=mid+1 ? right=mid 还是 right=mid-1 ?

3、二分查找标准模板与变体

精确二分查找模板（不保留 $m i d$ 在区间）

例如给定有序数组 $[1, 3, 5, 6, 9, 13]$ ，查找数字 $5$ 的下标代码如下：

/**
请注意这是非常简单标准的折半查找模板，这里注意一定要是 left<=right ，因为三个指针可以同时指向一个元素，
凡是写了left<=right的话就一定要注意left 与 right 中的mid都要 +1 or -1 ，
否则若只有两个元素 mid = (left+right)/2 = left 的话会进入死循环。 
**/
int BinarySearch(int [] nums,int key){
    int len = nums.size();
    int left = 0;
    int right =len-1;
    int mid = -1;

    while(left<=right){  //允许left、right、mid三者指向一个元素
        mid = left + (right-left)/2;
        if(nums[mid] == key){  //非常重要的判断条件
            return mid;
        }else if(nums[mid]<key){
            left = mid+1;     //严格往右折半
        }else{
            right = mid-1；   //严格往左折半
        }
    }
    return mid;
}

/*总结：left<=right ，需要配合left = mid+1 、right = mid-1
while 判断结束时只会出现两种情况：left/mid , right (left, mid 指向同一个数，right指向它的下一个数)
left/mid/right （left, mid, right 指向同一个数）
*/

查找左/右边界模板(保留mid的情况)

给定有序数组 $[1, 3, 3, 3, 9, 13]$ ，例 $1$ 查找数字 $3$ 首次出现的下标，例 $2$ 查找 $3$ 数组最后一次出现的下标，如果直接套用上面的代码则会查找任意一个 $3$ 。使用二分的思维来思考此问题，首先mid的判断条件完全不是上题的nums[mid] == key，因为就算找到这个mid也无法保证是最左边的，
本题在while循环中没有判断终止条件，完全靠while()中的判断终止，这里千万注意left<right与left =mid，right =mid的矛盾。当找到了nums[mid] == key时，我们还需要搜索[0,mid-1]区间中是否存在满足条件的mid。此时有两种情况，一种是[0,mid-1]不存在key,另一种就是存在key，无论哪一种情况都可以看成查找[0,mid]区间，此区间一定存在key。所以当考虑了等于的情况时，本题就是搜索的时候需要保留mid在区间里面，如果是考虑在左边则是搜索区间[0,mid]，else 里面写[mid+1,len]即可。这里有个小技巧，一般我会在注释里写上「下一轮搜索区间是什么」。如果下一轮搜索区间是[mid..right]，这个时候就设置 left = mid，这种情况的反面区间就是[left..mid - 1] ，那么 else 就设置right = mid - 1。现在出现了mid不加1的情况，所以这里会出现死循环的情况当只有两个元素时[0,1],left = 0,right = 1,mid = (left+right)/2=0, left = mid = 0 < right，循环永远跳不出去，而且这是因为mid向下取整导致的，所以重点就是当 left = mid 时，需要向上取整（向right取整）mid = left+(right-left)/2+1;否则当right = mid时，得下取整（向left取整），mid =left+(right-left)/2+1 ;

代码如下：
```
//=========================================左区间查找=================================================
int BinarySearch(vector<int> nums,int key){
    int len = nums.size();
    int left = 0;
    int right =len-1;
    int mid = -1;

    while(left<right){        //因为 right = mid 所以，不能取等号
        mid = left + (right-left)/2 ;  //向left取整(向下取整)，因为right = mid会进入死循环。 

        if (nums[mid]>=key){
            right = mid;       //往右折半,因为有等于的可能，所以包含 mid 在里面，不能 right = mid + 1 跳过mid
        }else{
            left = mid+1;   //往左折半，这里可以判断出mid一定不是我们要的，所以可以跳过，让然也可以写成 left = mid 。
        }
    }
    return left;
}

//=========================================右区间查找=================================================

int BinarySearch(vector<int> nums,int key){
    int len = nums.size();
    int left = 0;
    int right =len-1;
    int mid = -1;

    while(left<right){        //因为 left = mid 所以，不能取等号
        mid = left + (right-left)/2 + 1;  //向right取整(向上取整)，因为left = mid 会进入死循环。 

        if (nums[mid]<=key){
            left = mid;       //往右折半,因为有等于的可能，所以包含 mid 在里面，不能 left = mid + 1 跳过mid
        }else{
            right = mid-1;   //往左折半，这里可以判断出mid一定不是我们要的，所以可以跳过，让然也可以写成 right = mid 。
        }
    }
    return right;
}

//总结：有人会说，那我改成 while(left<=right)，不就可以不用 mid = left + (right-left)/2+1 了吗！错！，如果改成left<=right
//那么mid = left + (right-left)/2+1; 与 mid=left+(right-left)/2都失去了作用，因为当left==mid==right时，无论向上取整还是
//向下取整都无力回天。left < right，时只有 left=mid 或者 right=mid 会出问题，我们调整向上向下取整即可避免陷入死循环。
//大概可以理解为 left<right 扔掉等号，仅仅让其中一半不陷入死循环，另一半通过调整向上向下取整来避免死循环。
```

左边界二分查找 2

左边界查找的第二种类型用于数组部分有序且包含重复元素的情况，这种条件下在我们向左收缩的时候，不能简单的令 right = mid，因为有重复元素的存在，这会导致我们有可能遗漏掉一部分区域，此时向左收缩只能采用比较保守的方式，代码模板如下：

class Solution {
    public int search(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) {
                left = mid + 1;
            } else if (nums[mid] > target) {
                right = mid;
            } else {
                right--;
            }
        }
        return nums[left] == target ? left : -1;
    }
}

例题：https://leetcode-cn.com/problems/find-minimum-in-rotated-sorted-array-ii/

查找左右边界

只需要分别查找左边界和右边界就可以，代码如下：

class Solution {
    public int[] searchRange(int[] nums, int target) {
        int[] res = new int[]{-1, -1};
        if(nums == null || nums.length == 0) return res;
        // find the left-end
        int left = 0;
        int right = nums.length - 1;
        while (left < right) {
            int mid = left + ((right - left) >> 1);
            if (nums[mid] < target) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        res[0] = nums[left] == target ? left : -1;
        
        // find right-end
        if (res[0] != -1) {
            if (left == nums.length - 1 || nums[left + 1] != target) {
                res[1] = left;
            } else {
                right = nums.length - 1;
                while (left < right) {
                    int mid = left + ((right - left) >> 1) + 1;
                    if (nums[mid] > target) {
                        right = mid - 1;
                    } else {
                        left = mid;
                    }
                }
                res[1] = right;
            }
        }
        return res;
    }
}

例题：https://leetcode.com/problems/find-first-and-last-position-of-element-in-sorted-array/

总结为如下表，其实不需要死记硬背，重在理解！再来一遍理解，当left<=right时，都需要 mid +1或者 mid-1 。如果判断条件是left < right 则若

left = mid则向上(右)取整 , (left + right) / 2 + 1; 否则 right = mid时，向下(左)取整(left + right) / 2 。

查找方式	循环条件	左侧更新	右侧更新	中间点位置	返回值
标准二分查找	`left <= right`	`left = mid - 1`	`right = mid + 1`	`(left + right) / 2`	`-1 / mid`
二分找左边界	`left < right`	`left = mid - 1`	`right = mid`	`(left + right) / 2`	`-1 / left`
二分找右边界	`left < right`	`left = mid`	`right = mid - 1`	`(left + right) / 2 + 1`	`-1 / right`

至此，二分查找的所有内容基本上介绍完毕，后续见到了其他类型再做补充！

精准查找细节处理案例1

LeetCode 33题点击查看题目！

此题为部分有序的题型，其实二分查找并不需要全部有序，只需要能够判断丢弃一半的数组的条件出现即可。本题的判断条件是查找有序的一半数组，因为有序的一半一定会尾部大于首部，nums=[9,11,7,8,9] ,nums[mid]=7, 因为nums[right]=9>=nums[mid] 所以右边有序，我们只需要在有序的一半里面查找是否target大于这部分有序的首部并且小于它的尾部即可。但是此题说起来简单，细节确实无比的复杂，必须考虑到nums若只有一个或者两个元素怎么办！若只有一个元素，那么这个元素是有序的吗？等等，请先看到此处自行实现代码再接着往下看代码实现：

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int len=nums.size();
        int left=0;
        int right=len-1;
        int mid=-1;

        while(left<=right){  //记得这是精确查找类题目，要保证left、right不能直接等于mid
            mid=left+(right-left)/2;
            if(nums[mid]==target)
                return mid; 
            //查找有序的一半区间，看看是否需要舍弃，千万注意是>= 还是 > ，非常重要要想清楚，不然很难！
            else if(nums[mid]>=nums[left]){
                //左边有序
                if(nums[mid]>=target && target>=nums[left]){
                    //target在左边
                    right=mid-1;
                }else{
                    left=mid+1;
                }
                
            }else if(nums[mid]<=nums[right]){
                //右边有序
                if(nums[mid]<=target && target<=nums[right]){
                    //target在右边
                    left=mid+1;
                }else{
                    right=mid-1;
                }
                
            }
        }
        return -1;
    }
};

执行结果