二分查找模板全面总结

桃扇骨 2023-09-30 10:36 79阅读 0赞

#### 二分查找 ####

*  二分法的引入
 *   *  情形1
     *   *  1.X的平方根
         *  2.搜索旋转排序数组
     *  情形2
     *   *  1.第一个错误的版本
         *  2.寻找峰值
         *  3.寻找旋转排序数组中的最小值
     *  情形3
     *   *  在排序数组中查找第一个和最后一个位置

当遇到查找特定元素的时候，最容易想到的就是暴力解法，直接遍历，这种做法简单粗暴，可以解题，但是时间复杂度过高。所以我们可以用二分法来提高效率。

## 二分法的引入 ##

二分查找一般用于数据是有序的，我们要找到目标元素target,可以通过循环或者递归在每一次比较以后都把查找范围缩小一半，在剩下范围接着查找。接下来，我就来介绍一下二分查找。我总结了几种不同的清况用到的二分模板，不过大家还是要自己动手做题，多画图。

### 情形1 ###

二分查找最基本的形式就是查找条件可以不需要和元素两侧进行比较来确定。

初始条件：left = 0, right = length-1  
终止：left > right  
向左查找：right = mid-1  
向右查找：left = mid+1

模板一的代码

int binarySearch(int[] nums, int target){
        
    //如果数组为空或者长度为0，我们肯定找不到我们想要查找的元素
      if(nums == null || nums.length == 0)
        return -1;
    //用左右指针来分别指向查找区间的左边界和右边界
      int left = 0, right = nums.length - 1;
      while(left <= right){
        
        //  这边涉及到数据溢出的问题
        int mid = left + (right - left) / 2;
        if(nums[mid] == target){
         return mid; }
        else if(nums[mid] < target) {
         left = mid + 1; }
        else {
         right = mid - 1; }
      }
    
      //  
      return -1;
    }

mid=(left+right)/2也可以，那为什么要写成mid=left+(right-left)/2;  
这是为了防止数据溢出，假设数据最多存储范围是0~255。  
left=200,right=240,这个时候在执行left+right的时候就已经超过范围了，所以为了防止数据溢出要写成mid=left+(right-left)/2

接下来通过实战来检验一下自己的学习成果

#### 1.X的平方根 ####

[力扣–X的平方根][X]

> 题目描述  
> 给你一个非负整数 x ，计算并返回 x 的 算术平方根 。
> 
> 由于返回类型是整数，结果只保留 整数部分 ，小数部分将被 舍去 。
> 
> 注意：不允许使用任何内置指数函数和算符，例如 pow(x, 0.5) 或者 x \*\* 0.5 。
> 
> 示例 1：
> 
> 输入：x = 4 输出：2 示例 2：
> 
> 输入：x = 8 输出：2 解释：8 的算术平方根是 2.82842…, 由于返回类型是整数，小数部分将被舍去。
> 
> 来源：力扣（LeetCode）

class Solution {
        
        public int mySqrt(int x) {
        
            //二分查找，由于是找算数平方根，所以肯定找得到
            //如果是0或1的话，直接返回
            if(x==0 || x==1) return x;
            //开始找
            int low=1;
            int high=x;
            int mid;
            while( low <=high){
        
                mid=(low + high)/2;
                if(mid> x /mid){
        
                    high=mid-1;
                }else if(mid  < x/mid){
        
                    low=mid+1;
                }else{
        
                    return mid;          
                }
            }
            return high;
        }
    }

为什么当条件不满足的时候，要返回low-1或high,我来说明一下，以目标元素是8为例。  
![在这里插入图片描述][watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBASmF2YeeahOWtpuS5oOS5i-i3rw_size_20_color_FFFFFF_t_70_g_se_x_16]

#### 2.搜索旋转排序数组 ####

[力扣-搜索旋转排序数组][-]  
题目描述

> 整数数组 nums 按升序排列，数组中的值 互不相同 。
> 
> 在传递给函数之前，nums 在预先未知的某个下标 k（0 <= k < nums.length）上进行了 旋转，使数组变为  
> \[nums\[k\], nums\[k+1\], …, nums\[n-1\], nums\[0\], nums\[1\], …,  
> nums\[k-1\]\]（下标 从 0 开始 计数）。例如， \[0,1,2,4,5,6,7\] 在下标 3 处经旋转后可能变为  
> \[4,5,6,7,0,1,2\] 。
> 
> 给你 旋转后 的数组 nums 和一个整数 target ，如果 nums 中存在这个目标值 target ，则返回它的下标，否则返回 -1  
> 。
> 
> 示例 1：
> 
> 输入：nums = \[4,5,6,7,0,1,2\], target = 0 输出：4 示例 2：
> 
> 输入：nums = \[4,5,6,7,0,1,2\], target = 3 输出：-1 示例 3：
> 
> 输入：nums = \[1\], target = 0 输出：-1
> 
> 提示：
> 
> 1 <= nums.length <= 5000  
> \-10^4 <= nums\[i\] <= 10^4 nums 中的每个值都 独一无二 题目数据保证 nums 在预先未知的某个下标上进行了旋转  
> \-10^4 <= target <= 10^4
> 
> 来源：力扣（LeetCode）  
> 链接：https://leetcode-cn.com/problems/search-in-rotated-sorted-array

class Solution {
        
        public int search(int[] nums, int target) {
        
     int low = 0, high = nums.length - 1, mid = 0;
        while (low <=high) {
        
            mid = low + (high - lo) / 2;
            if (nums[mid] == target) {
        
                return mid;
            }
            // 先根据 nums[mid] 与 nums[low] 的关系判断 mid 是在左段还是右段 
            if (nums[mid] >= nums[low]) {
        
                // 再判断 target 是在 mid 的左边还是右边，从而调整左右边界 low 和 high
                if (target >= nums[low] && target < nums[mid]) {
        
                    high = mid - 1;
                } else {
        
                    low = mid + 1;
                }
            } else {
        
                if (target > nums[mid] && target <= nums[high]) {
        
                    low = mid + 1;
                } else {
        
                    high = mid - 1;
                }
            }
        }
        return -1;
    
      
        }
    }

思路分析  
![在这里插入图片描述][watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBASmF2YeeahOWtpuS5oOS5i-i3rw_size_20_color_FFFFFF_t_70_g_se_x_16 1]

### 情形2 ###

查找条件需要访问元素的相邻的右边元素。  
根据是否满足条件，来决定是向左还是向右。  
保证查找空间在每一步中至少有 2 个元素。  
需要进行后处理。 当你剩下 1 个元素时，循环 / 递归结束。 需要评估剩余元素是否符合条件。

初始条件：left = 0, right = length  
终止：left == right  
向左查找：right = mid  
向右查找：left = mid+1

#### 1.第一个错误的版本 ####

[力扣-第一个错误的版本][- 1]

> 你是产品经理，目前正在带领一个团队开发新的产品。不幸的是，你的产品的最新版本没有通过质量检测。由于每个版本都是基于之前的版本开发的，所以错误的版本之后的所有版本都是错的。
> 
> 假设你有 n 个版本 \[1, 2, …, n\]，你想找出导致之后所有版本出错的第一个错误的版本。
> 
> 你可以通过调用 bool isBadVersion(version) 接口来判断版本号 version  
> 是否在单元测试中出错。实现一个函数来查找第一个错误的版本。你应该尽量减少对调用 API 的次数。
> 
> 示例 1：
> 
> 输入：n = 5, bad = 4 输出：4 解释： 调用 isBadVersion(3) -> false 调用  
> isBadVersion(5) -> true 调用 isBadVersion(4) -> true 所以，4 是第一个错误的版本。 示例  
> 2：
> 
> 输入：n = 1, bad = 1 输出：1
> 
> 作者：力扣 (LeetCode)  
> 链接：https://leetcode-cn.com/leetbook/read/binary-search/xepthr/

这题就是要找到第一个出现错误的版本，如果当前版本正确，继续往下找之后的版本，如果当前版本错误，就看一下上一个版本是否正确，因为题目说出现错误版本，说明最后肯定有错误的版本。

/* The isBadVersion API is defined in the parent class VersionControl.
          boolean isBadVersion(int version); */
    
    public class Solution extends VersionControl {
        
        public int firstBadVersion(int n) {
        
            int low=1;
            int high=n;
            int mid;
            while(low<high){
        
                mid=low+(high-low)/2;
               if(isBadVersion(mid)){
        
                   //区间在[low,mid]
                   high=mid;
               }else{
        
                   low=mid+1;
               }
              
            }
           
            return low;
            
        }
    }

#### 2.寻找峰值 ####

[力扣-寻找峰值][- 2]  
![在这里插入图片描述][watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBASmF2YeeahOWtpuS5oOS5i-i3rw_size_20_color_FFFFFF_t_70_g_se_x_16 2]  
我们可以看出来这题他肯定是有峰值的，我们可以用二分法，然后比较当前元素和相邻元素的大小，通过二分不断逼近。

class Solution {
        
        public int findPeakElement(int[] nums) {
        
    
            int low=0;
            int high=nums.length-1;
            int mid;
            while(low < high){
        
                mid=low+(high-low)/2;
                if(nums[mid] > nums[mid+1] ){
        
                    //说明峰值在左边
                    high=mid;
                }else{
        
                    low=mid+1;
                }
    
            }
            return low;
                        
     
    
        }
    }

#### 3.寻找旋转排序数组中的最小值 ####

这道题目挺有难度的，大家可以仔细想想  
![在这里插入图片描述][watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBASmF2YeeahOWtpuS5oOS5i-i3rw_size_20_color_FFFFFF_t_70_g_se_x_16 3]  
![在这里插入图片描述][watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBASmF2YeeahOWtpuS5oOS5i-i3rw_size_20_color_FFFFFF_t_70_g_se_x_16 4]

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

### 情形3 ###

每一次查找范围中都有三个元素，要根据相邻元素来进行比较，从而判断向左还是向右  
初始条件：left = 0, right = length-1  
终止：left + 1 == right  
对于我们初学的来来说，我们应该分别计算左边界和右边界，不要想着一下子解决，做题目要有耐心，不要想当然，多画图，可能画图分析自己就会了。

#### 在排序数组中查找第一个和最后一个位置 ####

[在排序数组中查找第一个和最后一个位置][Link 1]  
![在这里插入图片描述][watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBASmF2YeeahOWtpuS5oOS5i-i3rw_size_20_color_FFFFFF_t_70_g_se_x_16 5]  
分析:  
根据题目要求，我们知道目标元素在数组中可能出现多次，所以我们就需要找到这个元素的左边界和右边界，我们就可以使用两个二分查找来找到左边界和右边界。  
![在这里插入图片描述][watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBASmF2YeeahOWtpuS5oOS5i-i3rw_size_20_color_FFFFFF_t_70_g_se_x_16 6]

class Solution {
        
        public int[] searchRange(int[] nums, int target) {
        
           int leftBorder = getLeftBorder(nums, target);
            int rightBorder = getRightBorder(nums, target);
            // 情况一
            if (leftBorder == -2 || rightBorder == -2) return new int[]{
        -1, -1};
            // 情况三
            if (rightBorder - leftBorder > 1) return new int[]{
        leftBorder + 1, rightBorder - 1};
            // 情况二
            return new int[]{
        -1, -1};
        }
    
        int getRightBorder(int[] nums, int target) {
        
            int left = 0;
            int right = nums.length - 1;
            int rightBorder = -2; // 记录一下rightBorder没有被赋值的情况
            while (left <= right) {
        
                int middle = left + ((right - left) / 2);
                if (nums[middle] > target) {
        
                    right = middle - 1;
                } else {
         // 寻找右边界，nums[middle] == target的时候更新left
                    left = middle + 1;
                    rightBorder = left;
                }
            }
            return rightBorder;
        }
    
        int getLeftBorder(int[] nums, int target) {
        
            int left = 0;
            int right = nums.length - 1;
            int leftBorder = -2; // 记录一下leftBorder没有被赋值的情况
            while (left <= right) {
        
                int middle = left + ((right - left) / 2);
                if (nums[middle] >= target) {
         // 寻找左边界，nums[middle] == target的时候更新right
                    right = middle - 1;
                    leftBorder = right;
                } else {
        
                    left = middle + 1;
                }
            }
            return leftBorder;
        }
    }

[X]: https://leetcode-cn.com/problems/sqrtx/
[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBASmF2YeeahOWtpuS5oOS5i-i3rw_size_20_color_FFFFFF_t_70_g_se_x_16]: https://img-blog.csdnimg.cn/7faf9229125c455283e9d6ad03ea3f43.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBASmF2YeeahOWtpuS5oOS5i-i3rw==,size_20,color_FFFFFF,t_70,g_se,x_16
[-]: https://leetcode-cn.com/problems/search-in-rotated-sorted-array/
[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBASmF2YeeahOWtpuS5oOS5i-i3rw_size_20_color_FFFFFF_t_70_g_se_x_16 1]: https://img-blog.csdnimg.cn/95ad0c4645134e44b26fcdc154884e66.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBASmF2YeeahOWtpuS5oOS5i-i3rw==,size_20,color_FFFFFF,t_70,g_se,x_16
[- 1]: https://leetcode-cn.com/problems/first-bad-version/
[- 2]: https://leetcode-cn.com/leetbook/read/binary-search/xem7js/
[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBASmF2YeeahOWtpuS5oOS5i-i3rw_size_20_color_FFFFFF_t_70_g_se_x_16 2]: https://img-blog.csdnimg.cn/4681655a463e46059f73fa16cb00aa5b.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBASmF2YeeahOWtpuS5oOS5i-i3rw==,size_20,color_FFFFFF,t_70,g_se,x_16
[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBASmF2YeeahOWtpuS5oOS5i-i3rw_size_20_color_FFFFFF_t_70_g_se_x_16 3]: https://img-blog.csdnimg.cn/e7fc9c55152f4fdfb16b5a427ffe0f04.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBASmF2YeeahOWtpuS5oOS5i-i3rw==,size_20,color_FFFFFF,t_70,g_se,x_16
[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBASmF2YeeahOWtpuS5oOS5i-i3rw_size_20_color_FFFFFF_t_70_g_se_x_16 4]: https://img-blog.csdnimg.cn/3313a2dc0d72431c97b6af178272df54.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBASmF2YeeahOWtpuS5oOS5i-i3rw==,size_20,color_FFFFFF,t_70,g_se,x_16
[Link 1]: https://leetcode-cn.com/leetbook/read/binary-search/xenp13/
[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBASmF2YeeahOWtpuS5oOS5i-i3rw_size_20_color_FFFFFF_t_70_g_se_x_16 5]: https://img-blog.csdnimg.cn/482e673a2d07439da3b797eacf02ccf1.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBASmF2YeeahOWtpuS5oOS5i-i3rw==,size_20,color_FFFFFF,t_70,g_se,x_16
[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBASmF2YeeahOWtpuS5oOS5i-i3rw_size_20_color_FFFFFF_t_70_g_se_x_16 6]: https://img-blog.csdnimg.cn/6ef72c85c011436bb58dc3bdc6dd870d.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBASmF2YeeahOWtpuS5oOS5i-i3rw==,size_20,color_FFFFFF,t_70,g_se,x_16