二分查找的细节总结
二分查找的细节总结
最近把leetcode上关于二分查找的简单题都刷差不多了,leetcode给我的技能树上点了二分查找
二分查找大概有几类：
- 二分查找值后返回(唯一) 标准二分查找 比如: 704. 二分查找
- 寻找应该插入的下标 寻找左边界 比如: 35. 搜索插入位置
- 给定一个值，寻找应该插入的下标 寻找右边界 1618. 找出适应屏幕的最大字号
- 山脉数组，旋转数组 153. 寻找旋转排序数组中的最小值
1.while循环的条件
为什么 while 循环的条件中有的人用的是 <=，有的是<呢。
这取决于初始化 right的赋值是 nums.length - 1还是 nums.length
我们要搜索的区间,当<=时 我们搜索的区间为[left, right],而<是相当于左闭右开区间 [left, right)的
<=的结束循环条件是 left+1=right
<的结束循环条件是 left=right
所以当使用while(left < right)的时候 ,最后一次left=right是没有进入循环的，需要单独判断一次是否符合条件。
2.中间值mid
关于取中间数 mid = (left + right) / 2;
在 left + right 很大的时候会发生整形溢出，一般这样改写：mid = left + (right - left) / 2
还有一个细节，/ 2 表示的是下取整，当数组中的元素个数为偶数的时候，只能取到位于左边的那个元素
取右边中间数的表达式是mid = left + (right - left + 1) / 2
3.二分的区间划分
普通的二分查找，把区间分成三段，left mid right
我的二分模板为:
public int binarySearch(int[] nums, int target) {
if (nums.length == 0) return -1;
int left = 0;
int right = nums.length - 1;
while (left < right) {
int mid = left + (right-left) /2;
if (target == nums[mid]) {
return mid;
} else if (target > nums[mid]) {
left = mid + 1;
} else {
right = mid - 1;
}
}
//因为在上方while条件中 我的终止条件是left=right，所以我需要判断最后left是否符合要求
return left==target ? left:-1;
}左边界查找
但是当数组为[1,2,2,3,3,4,5,6] ，target为2时，我们需要找到最小的下标时，上面的模板不管用了。
这时候我们会把搜索区间分为两部分，mid归哪一部分呢
在上面第二点中讲到过因为/ 2 表示的是下取整所以mid = left + (right - left) / 2是永远也取不到右边界right的所以 右边的图的归法 会产生死循环退不出问题。
以下是我的左边界查找模板:
public int binarySearch(int[] nums, int target) {
if (nums.length == 0) return -1;
int left = 0;
int right = nums.length-1;
while (left < right) {
int mid = left + (right-left) /2;
if (nums[mid] >= target) {
// 下一轮搜索区间是 [left, mid]
right = mid;
} else
// 下一轮搜索区间是 [mid + 1, right)
left = mid + 1;
}
}
//理由同上
return nums[left] == target ? left : -1;
}右边界查找
当数组为[1,2,2,4] ，target为2时，我们需要找到最大的下标
public int binarySearch(int[] nums, int target) {
if (nums.length == 0) return -1;
int left = 0;
int right = nums.length;
while (left < right) {
int mid = left + (right-left) /2;
if (nums[mid] >= target) {
// 下一轮搜索区间是 [mid, right]
left = mid + 1;
} else
// 下一轮搜索区间是 [left mid)
right = mid;
}
}
//最后要检查 越界的情况
if(left-1<0)
return -1;
//理由同上
return nums[left-1] == target ? left-1 : -1;
}为什么最后返回 left - 1 而不像左侧边界的函数，返回 left
首先，while 循环的终止条件是 left == right，所以 left 和 right 是一样的。
至于为什么要减一，这是搜索右侧边界的一个特殊点，关键在这个条件判断
if (nums[mid] >= target) {
left = mid + 1;
}当nums[mid]==target时
while 循环结束时，nums[left] 一定不等于 target 了，而 nums[left-1] 可能是 target。
本站文章除注明转载/出处外，均为本站原创，转载前请务必署名,转载请标明出处
腾讯云开发者
