devbox
羊村懒王
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

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

作者：羊村懒王 | 2024-04-08 22:52:10

赞

踩

二分查找

  

            

目录

1.二分查找是干啥的

2. 力扣中的一些练习题

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

2.2 第一个错误的版本

 2.3 搜索插入位置

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

2.5 x的平方根

 2.6 有效的完全平方数

3.总结一下

1.二分查找是干啥的

二分查找（Binary Search）也叫作折半查找。

是在有序数组中，寻找一个数字，然后返回其对应要求的值，二分查找相比于暴力求解，算法效率是比较高的。

二分查找有两个要求，一个是数列有序，另一个是数列使用顺序存储结构（比如数组）。

二分查找的算法思想是

 

2. 力扣中的一些练习题

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

链接   704. 二分查找 - 力扣（LeetCode） 

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

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

 第一种写法  

定义 target 在一个在左闭右闭的区间里，也就是[left, right] 这个中，

区间的定义决定了二分法的代码应该怎么样写

因为定义在了这个区间中，所以考虑下面两点

循环while结束的条件是什么   

while (left <= right) 要使用 <= ，因为left == right是有意义的，所以使用 <=

给left和right赋什么值

if (nums[mid]< target) left 要赋值为 mid + 1，因为当前这个nums[mid]一定不是target，那么接下来要查找的左区间结束下标位置就是 mid + 1

  1. class Solution {
  2.     public int search(int[] nums, int target) {
  3.         //target定义在左闭右闭的区间里，[left,right]
  4.         int left = 0;
  5.         int right = nums.length-1;
  6.         while(left <= right){
  7.         //当left==right，区间[left,right]依然有效，所以用<=
  8.             int mid = left + (right-left)/2;
  9.             if(nums[mid] == target){
  10.                 return mid;
  11.             }else if(nums[mid] < target){
  12.                 left = mid + 1;
  13.         //target在右区间,所以[mid+1,right]
  14.             }else{
  15.         //(nums[mid]>target)target在左区间,所以[left,mid-1]
  16.                 right = mid - 1;
  17.             }
  18.         }
  19.         return -1;
  20.     }
  21. }

第二种写法

定义 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]

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

  1. class Solution {
  2. public:
  3.     int search(vector<int>& nums, int target) {
  4.         int left = 0;
  5.         int right = nums.size(); 
  6.        // 定义target在左闭右开的区间里，即：[left, right)
  7.         while (left < right) { 
  8.       //因为left==right的时候，在[left, right)是无效的空间，所以使用<
  9.             int mid = left + ((right - left) >> 1);
  10.             if (nums[mid] > target) {
  11.                 right = mid; 
  12.        // target 在左区间，在[left, mid)中
  13.             } else if (nums[mid] < target) {
  14.                 left = mid + 1;
  15.       // target 在右区间，在[mid + 1, right)中
  16.             } else { // nums[mid] == target
  17.                 return mid; 
  18.             }
  19.         }
  20.         // 未找到目标值
  21.         return -1;

2.2 第一个错误的版本

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

分析一下

  1. /* The isBadVersion API is defined in the parent class VersionControl.
  2.       boolean isBadVersion(int version); */
  3.  
  4. public class Solution extends VersionControl {
  5.     public int firstBadVersion(int n) {
  6.         
  7.         int left = 1, right = n;
  8.         while(left < right){
  9.             int mid = left + (right - left) / 2;
  10.             if(isBadVersion(mid)){
  11.                 right = mid ;
  12.             }else{
  13.                 left = mid + 1;
  14.             }
  15.         }
  16.         return right;
  17.     }
  18. }

 2.3 搜索插入位置

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

 分析一下

 

  1. class Solution {
  2.     public int searchInsert(int[] nums, int target) {
  3.         int left = 0;
  4.         int right = nums.length-1;
  5.         while(left<=right){
  6.             int mid = left + (right - left)/2;
  7.             if(nums[mid] > target){
  8.                 right = mid - 1;
  9.             }else if(nums[mid] < target){
  10.                 left = mid + 1;
  11.             }else{
  12.                 return mid;
  13.             }
  14.         }
  15.          return right+1;
  16.     }
  17. }

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

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

 

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

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

找左边界

  1.     public int getLeftBorder(int[] nums, int target){
  2.         int left = 0;
  3.         int right = nums.length - 1;
  4.         int leftBorder = -2;//用来记录leftBorder没有被赋值的情况
  5.         while(left <= right){
  6.             int mid = left + (right - left);
  7.                 if(nums[mid] >= target){
  8.                 //寻找左边界
  9.                     right = mid - 1;
  10.                     leftBorder = right;
  11.                 }else{
  12.                     left = mid + 1;
  13.                 }
  14.             }
  15.         return leftBorder;
  16.     }

找右边界

  1.     public int getRightBorder(int[] nums, int target){
  2.         int left = 0;
  3.         int right = nums.length - 1;
  4.         int rightBorder = -2;
  5.         while(left <= right){
  6.             int mid = left + (right - left);
  7.                 if(nums[mid] > target){
  8.                     right = mid - 1;
  9.                 }else{
  10.                     //寻找右边界
  11.                     left = mid + 1;
  12.                     rightBorder = left;
  13.                 }
  14.             }
  15.         return rightBorder;    
  16.     }

分情况讨论了

  1.     public int[] searchRange(int[] nums, int target) {
  2.       int leftBorder = getLeftBorder(nums, target);
  3.       int rightBorder = getRightBorder(nums, target);
  4.       //数组中没有target，target在数组左边或右边
  5.       if(leftBorder == -2 || rightBorder == -2){
  6.           return new int[]{-1,-1};
  7.       }
  8.       //数组中有target，返回这两个target下标
  9.       if(rightBorder -leftBorder >1){
  10.           return new int[]{leftBorder + 1,rightBorder - 1};
  11.       }
  12.       //target在数组范围中，但数组不存在target
  13.       return new int[]{-1,-1};
  14.     }

2.5 x的平方根

链接    69. x 的平方根 - 力扣（LeetCode）

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

  1. class Solution {
  2.     public int mySqrt(int x) {
  3.         int left = 0;
  4.         int right = x;
  5.         int ans = -1;
  6.         while(left <= right){
  7.             int mid = left + (right -left)/2;
  8.             if((long)mid*mid <= x){
  9.           //这里写乘法的，必须要转成long，不然会溢出
  10.           //或者直接写除法，就不考虑溢出了
  11.                 ans = mid;
  12.                 left = mid + 1;
  13.             }else{
  14.                 right = mid -1;
  15.             }
  16.         }
  17.      return ans;
  18.     }
  19. }

 2.6 有效的完全平方数

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

 简单分析一下

  1. class Solution {
  2.     public boolean isPerfectSquare(int num) {
  3.         int left = 0;
  4.         int right = num;
  5.         while(left <= right){
  6.             int mid = left + (right - left)/2;
  7.             if((long)mid*mid < num){
  8.                 left = mid + 1;
  9.             }else if((long)mid*mid > num){
  10.                 right = mid - 1;
  11.             }else{
  12.                 return true;
  13.             }
  14.         }
  15.         return false;
  16.     }
  17. }

3.总结一下

见到数组的题，我们可以先看一下，有没有顺序，如果有，可以根据题意考虑可以合不合适使用二分查找。

然后再写二分查找时，如何保证你写的二分查找是正确的，可以多想一下这段话

要对区间定义想情楚，区间的定义就是不变量，这里建议可以多画画图.

要在二分查找过程中，保持不变量，就是要用while寻找每一次边界的处理，都要坚持根据区间的定义来操作，这就是循环不变量的规则。

写二分法，区间定义要想清楚，

一般有两种，左闭右闭 [ left , right ]       左闭右开  [ left , right )

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/羊村懒王/article/detail/388740
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号