备战蓝桥必做题型---二分查找算法，超详细讲解，算法小白也可以轻松掌握【详细讲解+例题+模板总结+例题链接】。

赛姐在努力.

1147人浏览 · 2024-10-27 14:00:00

赛姐在努力. · 2024-10-27 14:00:00 发布

提及二分查找算法，或许大多数人脑子里会有一个固定的想法就是数组必须是有序的，但其实不是的，任何一个题目只要分析出具有二段性（下文会做详细的解释）的都可以使用二分算法。好啦，废话不多说，上题感受一下！！

二分模板一

首先我们先来看一道简单的例题（例题链接：704. 二分查找 - 力扣（LeetCode））

算法原理讲解

当大家拿到这道题时，可能会先想到直接遍历一遍数组，然后找出目标 target ，当然这个方法是可行的，但是如果上面这道例题的 target 如果为12，那么就意味着需要遍历整个数组，才会找到目标值，时间复杂度也就是 O(N)，但是如果这道题我们用二分查找来做，时间复杂度可以缩短到O(logN)。

二分也就整个分成两半，首先来看 -1，0，3，5，9，12 此时将它分成一半（根据 0 和 12 的数组下标（（0+5）/2）=2）也就是下标为 2 所指向的 3 ，此时我们拿 3 和 9 做对比，3 是小于 9 的，又由题目知，数组是一个升序的，所以说当 3 小于 9 时，那么比 3 更小的 -1，0 更不可能了，所以说我们可以直接 pass 掉 3 及 3 左边的数字，此时我们主要需要查找的为 5 9 12 ，此时又根据二分（（3+5）/2=4）此时下标 4 所指向的数字 9 便是目标 target ，使用二分只需要两次便可以查找到结果。下面是图释。

代码展示

接下来在举一个简单的栗子，在 nums=[1,2,3,4,5,6,7,8,9,10,11,12,13] 中查找目标值为 target=9，并返回其下标。

由上面两个例子我们可以总结出模板一

 while(left<=right){
        int mid=(left+right)/2;
        if(……) 
           left=mid+1;
        else if(……) 
           right=mid-1;
        else 
           return ……;
    }

二分模板二

首先我们还是以例题起手（例题链接：34. 在排序数组中查找元素的第一个和最后一个位置 - 力扣（LeetCode））

查找左端点

现在以数组 nums=[5,7,7,8,8,10] 为例子，由 nums 可以看出，最终需要求的下标为 3 和 4 ，现在我们先求左边的端点，将数组分成 5，7，7 和 8，8，10 两段，可以明显看出左边全是比 target 小的，后面的数全是大于等于 target 的数，这里分成的两段就是上面所说的二段性。

按照上面的划分，利用二分来对问题进行求解，mid=(left+right)/2 ,mid=(0+5)/2=2，nums[2]<target 此时 nums[mid] 落在了 7 的位置由于划分时我们已经确保7是比 target 小的值，所以说此时令 ,left=mid+1,left=3 再次利用二分 mid=(left+right)/2,mid=(3+5)/2=4 ,nums[mid]=8,nums[mid]>=target，此时 mid 所在的下标落在了 8 的下面，但是注意此时这个8是右端点的8 不是左端点的 8 ，我们需要求解的为左端点的 8，此时我们应该让 right=mid,这里为什么是 right=mid呢？注意我们这里划分的 左边是小于 target 的，右边是大于等于 target 的，所以当遇见 nums[mid]>=target 时，应该让 right=mid，而不是right=mid-1，因为很有可能right所指的值就是最终我们需要求解的值。此时 left=3, right=4,mid=(3+4)/2=3，此时 nums[mid]>=target ，right=mid，此时 left=3, right=3，此时在利用一次二分 mid=(left+right)/2，mid=(3+4)/2=3，此时 mid 所指向的为左端点 8 。

注意到细节的同学可能会注意到一个点就是这个二分循环应该怎么暂停呢？因为需要查找的其实 8 ，在第一次查找到右边的 8 的时候，我们又该怎么去判断，这个 8 是不是最终那个结果的 8 呢？其实由上面标绿的可以看出，对应最终结果的 8 时，此时 left==right ，那为什么又是 right== left 呢？（下文会有解释）

查找右端点

当了解到了左端点的查找后，右端点的查找和左端点是一样的，此时需要将数组划分为 5，7，7，8，8 和 10，此时左区间是小于等于taregt 的，右区间是大于target 的，当 mid 落在左区间时（nums[mid]<=target），需要让 left=mid ，mid 落在右区间时(nums[mid]>target)，需要让 right=mid -1。

结果代码展示：

class Solution {
    public int[] searchRange(int[] nums, int target) {
        int left=0,right=nums.length-1,ret_left=-1,ret_right=-1;
        if(nums.length==0) return new int[]{ret_left,ret_right};
        
        //查找左端点
        while(left<right){
            int mid=left+(right-left)/2;
            if(nums[mid]>=target) right=mid;
            else if(nums[mid]<target) left=mid+1;
        }

        //判断左端点的结果
        if(nums[left]==target) ret_left=left;

        right=nums.length-1;
        //查找右端点
        while(left<right){
            int mid=left+(right-left+1)/2;
            if(nums[mid]>target) right=mid-1;
            else if(nums[mid]<=target) left=mid;
        }

        //判断右端点的结果
        if(nums[left]==target) ret_right=left;

        return new int[]{ret_left,ret_right};

    }
}

循环条件为while(left<right)

这里小编用大白话讲解查找左端点时的循环条件，查找右端点和查找左端点的循环条件是一样的。循环条件为 left<right ,也就是意味着当 left==right 时跳出循环。此时当它俩相遇时就可以判断，nums[left]==target，如果是相等的就说明找到了左端点，否则就是左端点不存在。

循环条件之所以可以写成 left<right 是因为当我们求左端点时，我们划分的区间是，小于 target 和大于等于 target 的，因此当 mid 落在了左区间，因为左区间一定不会存在目标值，所以此时 left=mid+1 ，left会直接利用 mid+1 ，直到走到第一个左端点的8 ，此时再使用二分时，就会是 mid 落在右区间，因为右区间规定的是大于等于target ，所以当 mid 落在右区间时，很有可能是目标值 target，因此 right=mid，因此 right 也会一直向左走，直到当 left==right ，此时 right 走到了 left 指向的左端点的 8 。

当查找右端点时是一样的，如果小于等于 target 时，left=mid，此时 left 会一直向右边去进行查找，如果大于 target 时，right=mid-1。left 一直向右边走，right不断的向左边走，直到最后 left和 right相遇。此时它俩指向的便为右端点的目标值。

mid 计算

在上面两个例子中，mid 的计算出现了三种不同的方法。

①：mid=(left+right)/2

②：mid=left+(right-left)/2 //防止溢出

③：mid=(right-left+1)/2

看似是三种，其实是两种，将②稍微变形一下就可以得到①，其中②和③的方法看起来很像，那他们又有什么区别？什么时候用②，什么时候又用③呢？当我们查找右端点时，如果在上面的例子中，假设现在只剩下了 8和10，8是要求的目标右端点，且此时left正指向右端点，如果使用第②个公式，算出来的mid指向的是8，此时nums[mid]<=target,left=mid,很显然，后面再进入循环后会死循环。此时如果我们拿出第③个公式来求mid，此时求出的mid指向的是10，nums[mid]>target,right=mid-1，后left==right，跳出循环，判断。

用大白话来说就是，当只有两个值的时候，我现在需要求解右端点。如果使用第②个公式的话，会无限的指向左边那个值，会使得left=mid，后进入循环，然后一直死循环，就永远出不去了。但是如果使用第③个就不会，说白了也就是当 right=mid-1 的时候，需要使用 mid=left+(right-left+1)/2 来求解mid。可以简记为 “right有-1，mid就有+1”

由上面的所有分析可以总结出模板二

         //求解左端点
        while(left<right){
            int mid=left+(right-left)/2;
            if(……) left=mid+1;
            else right=mid;
        }
        //判断
        ……
        
        //求解右端点
        while(left<right){
            int mid=left+(right-left+1)/2;
            if(……) right=mid-1;
            else left=mid;
        }
        //判断
        ……

例题篇

现在可以自己动手尝试一下，去实践上面的知识点。（注意：right有-1时，mid就有+1）

第一题：LCR 072. x 的平方根 - 力扣（LeetCode）

答案

class Solution {
    public int mySqrt(int x) {
        long left = 1, right = x;
        while (left < right) {
            long mid = left + (right - left + 1) / 2;
            if (mid * mid > x)
                right = mid - 1;
            else {
                left = mid;
            }
        }
        return (int)right;
    }
}

第二题：LCR 068. 搜索插入位置 - 力扣（LeetCode）

答案

class Solution {
    public int searchInsert(int[] nums, int target) {
        int ret=0,left=0,right=nums.length-1;
        if(target<nums[0]) return 0;
        if(target>nums[nums.length-1]) return nums.length;
        while(left<right){
            int mid=left+(right-left+1)/2;
            if(nums[mid]>target) right=mid-1;
            else left=mid;
        }
        if(nums[left]==target) return left;
        return left+1;
    }
}

第三题： LCR 069. 山脉数组的峰顶索引 - 力扣（LeetCode）

答案

class Solution {
    public int peakIndexInMountainArray(int[] arr) {
        int left = 0, right = arr.length - 1;
        while (left < right) {
            int mid = left + (right - left + 1) / 2;
            if (arr[mid] > arr[mid - 1])
                left = mid;
            else
                right = mid - 1;
        }
        return left;

    }
}

第四题：162. 寻找峰值 - 力扣（LeetCode）

答案

class Solution {
    public int findPeakElement(int[] nums) {
  int left=0,right=nums.length-1;
        while(left<right){
            int mid=left+(right-left)/2;
            if(nums[mid]>nums[mid+1]) right=mid;
            else left=mid+1;
        }
        return left;
    }
}

第五题：153. 寻找旋转排序数组中的最小值 - 力扣（LeetCode）

答案

class Solution {
    public int findMin(int[] nums) {
        int left = 0, right = nums.length - 1;
        int mid = left + (right - left) / 2;
        if (nums[mid] >= nums[0] && nums[mid] < nums[nums.length - 1])
            return nums[0];
        while (left < right) {
            mid = left + (right - left) / 2;
            if (nums[mid] >= nums[0])
                left = mid + 1;
            else
                right = mid;
        }
        return nums[left];
    }
}

以上就是本期分享的全部内容啦，有不对或者疑问的地方欢迎大家再评论区发言共同探讨~