【二分查找】有这一篇足够了

深碍√TFBOYSˉ_ 2023-09-29 13:47 6阅读 0赞

![1e923923913a422abd2e9e5bc9ef49c6.jpeg][]![e33154f4e4504ed4a1f65d51a9b13aae.jpeg][]

**目录**

1.二分查找是干啥的

2. 力扣中的一些练习题

2.1 二分查找(两种方法定义 target 是在一个在左闭右闭的区间里，也就是\[left, right\] )

2.2 第一个错误的版本

2.3 搜索插入位置

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

2.5 x的平方根

2.6 有效的完全平方数

3.总结一下

--------------------

## 1.二分查找是干啥的 ##

> **二分查找（Binary Search）也叫作[折半查找][Link 1]。**
> 
> **是在有序数组中，寻找一个数字，然后返回其对应要求的值，二分查找相比于暴力求解，算法效率是比较高的。**
> 
> **二分查找有两个要求，一个是数列有序，另一个是数列使用顺序存储结构（比如[数组][Link 2]）。**

二分查找的算法思想是

![08e7f9f44a16429ea9a257a0239c9649.png][]

![4dd97d17d5154d5f8010a47b20425a17.png][]

--------------------

## 2. 力扣中的一些练习题 ##

### 2.1 二分查找(两种方法定义 target 是在一个在左闭右闭的区间里，**也就是\[left, right\]** ) ###

链接 [704. 二分查找 - 力扣（LeetCode）][704. _ - _LeetCode]

![e14d09fc5c0f4471980f8a0828dddac1.png][]

这个题就是让在数组里找到这个数字，然后返回数字下标

因为力扣中的题是核心代码模式，所以我也就不写如何输入了

**第一种写法**

> **定义 target 在一个在左闭右闭的区间里，也就是\[left, right\] 这个中，**
> 
> **区间的定义决定了二分法的代码应该怎么样写**
> 
> 因为定义在了这个区间中，所以考虑下面两点
> 
> **循环while结束的条件是什么** 
> 
> while (left <= right) 要使用 <= ，因为left == right是有意义的，所以使用 <=
> 
> **给left和right赋什么值**
> 
> if (nums\[mid\]< target) left 要赋值为 mid + 1，因为当前这个nums\[mid\]一定不是target，那么接下来要查找的左区间结束下标位置就是 mid + 1

![718d5a26fac944b2b4c75aa7f0620642.png][]

class Solution {
        public int search(int[] nums, int target) {
            //target定义在左闭右闭的区间里，[left,right]
            int left = 0;
            int right = nums.length-1;
            while(left <= right){
            //当left==right，区间[left,right]依然有效，所以用<=
                int mid = left + (right-left)/2;
                if(nums[mid] == target){
                    return mid;
                }else if(nums[mid] < target){
                    left = mid + 1;
            //target在右区间,所以[mid+1,right]
                }else{
            //(nums[mid]>target)target在左区间,所以[left,mid-1]
                    right = mid - 1;
                }
            }
            return -1;
        }
    }

**第二种写法**

> **定义 target 在一个在左闭右开的区间里，也就是\[left, right) 这个中，**
> 
> **根据二分法的边界处理方式，就有不同的考虑**。
> 
> 因为定义在了这个区间中，所以考虑下面两点
> 
> **循环while结束的条件是什么** 
> 
> while (left < right) 要使用 <，因为left == right在区间\[left, right)是没有意义的
> 
> **给left和right赋什么值**
> 
> if (nums\[mid\] > target) right 更新为 mid，因为当前nums\[mid\]不等于target，去左区间继续寻找，而寻找区间是左闭右开区间，所以right更新为mid，即：下一个查询区间不会去比较nums\[mid\]

注意看和第一种方法中的图有什么不一样

![2819c685f2e54e64afdc048f98bb70c0.png][]

class Solution {
    public:
        int search(vector<int>& nums, int target) {
            int left = 0;
            int right = nums.size(); 
           // 定义target在左闭右开的区间里，即：[left, right)
            while (left < right) { 
          //因为left==right的时候，在[left, right)是无效的空间，所以使用<
                int mid = left + ((right - left) >> 1);
                if (nums[mid] > target) {
                    right = mid; 
           // target 在左区间，在[left, mid)中
                } else if (nums[mid] < target) {
                    left = mid + 1;
          // target 在右区间，在[mid + 1, right)中
                } else { // nums[mid] == target
                    return mid; 
                }
            }
            // 未找到目标值
            return -1;

--------------------

### 2.2 第一个错误的版本 ###

链接 [278. 第一个错误的版本 - 力扣（LeetCode）][278. _ - _LeetCode]

![9be36f4b3bc2404880735ceddd2fb3b7.png][]

分析一下

![b2925dbcc80c46439a234c7eabe0a8e5.png][]

/* 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 left = 1, right = n;
            while(left < right){
                int mid = left + (right - left) / 2;
                if(isBadVersion(mid)){
                    right = mid ;
                }else{
                    left = mid + 1;
                }
            }
            return right;
        }
    }

--------------------

### 2.3 搜索插入位置 ###

链接 [35. 搜索插入位置 - 力扣（LeetCode）][35. _ - _LeetCode]

![446b8c2bdcfd4e22a32922f57d3386d7.png][]

分析一下

![66481f6aebe94376879ad55f21cf0761.png][]

![3629699ac04a41b68501580729f89991.png][]

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){
                    right = mid - 1;
                }else if(nums[mid] < target){
                    left = mid + 1;
                }else{
                    return mid;
                }
            }
             return right+1;
        }
    }

--------------------

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

链接 [34. 在排序数组中查找元素的第一个和最后一个位置 - 力扣（LeetCode）][34. _ - _LeetCode]

![c8294b8905984fb3b7baba46f614b7aa.png][]

![50fcbc79949046ce83a0925d8c7fa3ba.png][]

这个题我们就可以使用二分查找来找它的左右边界

为了便于理解，我们寻找左右边界，分为两个二分查找写左右边界

**找左边界**

public int getLeftBorder(int[] nums, int target){
            int left = 0;
            int right = nums.length - 1;
            int leftBorder = -2;//用来记录leftBorder没有被赋值的情况
            while(left <= right){
                int mid = left + (right - left);
                    if(nums[mid] >= target){
                    //寻找左边界
                        right = mid - 1;
                        leftBorder = right;
                    }else{
                        left = mid + 1;
                    }
                }
            return leftBorder;
        }

**找右边界**

public int getRightBorder(int[] nums, int target){
            int left = 0;
            int right = nums.length - 1;
            int rightBorder = -2;
            while(left <= right){
                int mid = left + (right - left);
                    if(nums[mid] > target){
                        right = mid - 1;
                    }else{
                        //寻找右边界
                        left = mid + 1;
                        rightBorder = left;
                    }
                }
            return rightBorder;    
        }

**分情况讨论了**

public int[] searchRange(int[] nums, int target) {
          int leftBorder = getLeftBorder(nums, target);
          int rightBorder = getRightBorder(nums, target);
          //数组中没有target，target在数组左边或右边
          if(leftBorder == -2 || rightBorder == -2){
              return new int[]{-1,-1};
          }
          //数组中有target，返回这两个target下标
          if(rightBorder -leftBorder >1){
              return new int[]{leftBorder + 1,rightBorder - 1};
          }
          //target在数组范围中，但数组不存在target
          return new int[]{-1,-1};
        }

--------------------

### 2.5 x的平方根 ###

链接 [69. x 的平方根 - 力扣（LeetCode）][69. x _ - _LeetCode]

![e8c82292c79a492ba35a0a1ae8ae173e.png][]

分析一下（因为本篇是只讲解二分查找的，别的方法不提，主要加强二分查找理解）

![295b827c8fd740ab90060d78ee98c87d.png][]

class Solution {
        public int mySqrt(int x) {
            int left = 0;
            int right = x;
            int ans = -1;
            while(left <= right){
                int mid = left + (right -left)/2;
                if((long)mid*mid <= x){
              //这里写乘法的，必须要转成long，不然会溢出
              //或者直接写除法，就不考虑溢出了
                    ans = mid;
                    left = mid + 1;
                }else{
                    right = mid -1;
                }
            }
         return ans;
        }
    }

--------------------

### 2.6 有效的完全平方数 ###

链接 [367. 有效的完全平方数 - 力扣（LeetCode）][367. _ - _LeetCode]

![72c84b0f7f584dc6803f8db294d2a6cd.png][]

简单分析一下

![629df47f52fd4dce9e4e79a62d35eb16.png][]

class Solution {
        public boolean isPerfectSquare(int num) {
            int left = 0;
            int right = num;
            while(left <= right){
                int mid = left + (right - left)/2;
                if((long)mid*mid < num){
                    left = mid + 1;
                }else if((long)mid*mid > num){
                    right = mid - 1;
                }else{
                    return true;
                }
            }
            return false;
        }
    }

--------------------

## 3.总结一下 ##

> **见到数组的题，我们可以先看一下，****有没有顺序****，如果有，可以根据题意考虑可以合不合适使用二分查找。**
> 
> **然后再写二分查找时，如何保证你写的二分查找是正确的，可以多想一下这段话**
> 
> **要对区间定义想情楚**，**区间的定义就是不变量，这里建议可以多画画图.**
> 
> **要在二分查找过程中，****保持不变量，就是要用while寻找每一次边界的处理，都要坚持根据区间的定义来操作，这就是循环不变量的规则。**
> 
> **写二分法，区间定义要想清楚，**
> 
> **一般有两种，左闭右闭 \[ left , right \] 左闭右开 \[ left , right )**

--------------------

[1e923923913a422abd2e9e5bc9ef49c6.jpeg]: https://img-blog.csdnimg.cn/1e923923913a422abd2e9e5bc9ef49c6.jpeg
[e33154f4e4504ed4a1f65d51a9b13aae.jpeg]: https://img-blog.csdnimg.cn/e33154f4e4504ed4a1f65d51a9b13aae.jpeg
[Link 1]: http://data.biancheng.net/view/55.html
[Link 2]: http://data.biancheng.net/view/181.html
[08e7f9f44a16429ea9a257a0239c9649.png]: https://img-blog.csdnimg.cn/08e7f9f44a16429ea9a257a0239c9649.png
[4dd97d17d5154d5f8010a47b20425a17.png]: https://img-blog.csdnimg.cn/4dd97d17d5154d5f8010a47b20425a17.png
[704. _ - _LeetCode]: https://leetcode.cn/problems/binary-search/
[e14d09fc5c0f4471980f8a0828dddac1.png]: https://img-blog.csdnimg.cn/e14d09fc5c0f4471980f8a0828dddac1.png
[718d5a26fac944b2b4c75aa7f0620642.png]: https://img-blog.csdnimg.cn/718d5a26fac944b2b4c75aa7f0620642.png
[2819c685f2e54e64afdc048f98bb70c0.png]: https://img-blog.csdnimg.cn/2819c685f2e54e64afdc048f98bb70c0.png
[278. _ - _LeetCode]: https://leetcode.cn/problems/first-bad-version/
[9be36f4b3bc2404880735ceddd2fb3b7.png]: https://img-blog.csdnimg.cn/9be36f4b3bc2404880735ceddd2fb3b7.png
[b2925dbcc80c46439a234c7eabe0a8e5.png]: https://img-blog.csdnimg.cn/b2925dbcc80c46439a234c7eabe0a8e5.png
[35. _ - _LeetCode]: https://leetcode.cn/problems/search-insert-position/
[446b8c2bdcfd4e22a32922f57d3386d7.png]: https://img-blog.csdnimg.cn/446b8c2bdcfd4e22a32922f57d3386d7.png
[66481f6aebe94376879ad55f21cf0761.png]: https://img-blog.csdnimg.cn/66481f6aebe94376879ad55f21cf0761.png
[3629699ac04a41b68501580729f89991.png]: https://img-blog.csdnimg.cn/3629699ac04a41b68501580729f89991.png
[34. _ - _LeetCode]: https://leetcode.cn/problems/find-first-and-last-position-of-element-in-sorted-array/
[c8294b8905984fb3b7baba46f614b7aa.png]: https://img-blog.csdnimg.cn/c8294b8905984fb3b7baba46f614b7aa.png
[50fcbc79949046ce83a0925d8c7fa3ba.png]: https://img-blog.csdnimg.cn/50fcbc79949046ce83a0925d8c7fa3ba.png
[69. x _ - _LeetCode]: https://leetcode.cn/problems/sqrtx/
[e8c82292c79a492ba35a0a1ae8ae173e.png]: https://img-blog.csdnimg.cn/e8c82292c79a492ba35a0a1ae8ae173e.png
[295b827c8fd740ab90060d78ee98c87d.png]: https://img-blog.csdnimg.cn/295b827c8fd740ab90060d78ee98c87d.png
[367. _ - _LeetCode]: https://leetcode.cn/problems/valid-perfect-square/
[72c84b0f7f584dc6803f8db294d2a6cd.png]: https://img-blog.csdnimg.cn/72c84b0f7f584dc6803f8db294d2a6cd.png
[629df47f52fd4dce9e4e79a62d35eb16.png]: https://img-blog.csdnimg.cn/629df47f52fd4dce9e4e79a62d35eb16.png