【二分查找】有这一篇足够了
目录
1.二分查找是干啥的
2. 力扣中的一些练习题
2.1 二分查找
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
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)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]
注意看和第一种方法中的图有什么不一样
class Solution {public: int search(vector& nums, int target) { int left = 0; int right = nums.size(); // 定义target在左闭右开的区间里,即:[left, right) while (left < right) {//因为left==right的时候,在[left, right)是无效的空间,所以使用> 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)
分析一下
/* 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)
分析一下
class Solution { public int searchInsert(int[] nums, int target) { int left = 0; int right = nums.length-1; while(left target){ right = mid - 1; }else if(nums[mid] < target){ left = mid + 1; }else{ return mid; } } return right+1; }}
2.4 在排序数组中查找元素第一个和最后一个位置
链接 34. 在排序数组中查找元素的第一个和最后一个位置 - 力扣(LeetCode)
这个题我们就可以使用二分查找来找它的左右边界
为了便于理解,我们寻找左右边界,分为两个二分查找写左右边界
找左边界
public int getLeftBorder(int[] nums, int target){ int left = 0; int right = nums.length - 1; int leftBorder = -2;//用来记录leftBorder没有被赋值的情况 while(left = 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 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)
分析一下(因为本篇是只讲解二分查找的,别的方法不提,主要加强二分查找理解)
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)
简单分析一下
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){ right = mid - 1; }else{ return true; } } return false; }}
3.总结一下
见到数组的题,我们可以先看一下,有没有顺序,如果有,可以根据题意考虑可以合不合适使用二分查找。
然后再写二分查找时,如何保证你写的二分查找是正确的,可以多想一下这段话
要对区间定义想情楚,区间的定义就是不变量,这里建议可以多画画图.
要在二分查找过程中,保持不变量,就是要用while寻找每一次边界的处理,都要坚持根据区间的定义来操作,这就是循环不变量的规则。
写二分法,区间定义要想清楚,
一般有两种,左闭右闭 [ left , right ] 左闭右开 [ left , right )
2022深度学习开发者峰会 5月20日13:00让我们相聚云端,共襄盛会!