注册一亩三分地论坛，查看更多干货！
您需要 登录 才可以下载或查看附件。没有帐号？注册账号
x
本帖最后由 Falldawn 于 2024-5-2 10:45 编辑
之前写过一个帖子Binary Search for Beginners，最不易出错的 Binary Search写法和总结。
不过大佬 @wisdompeak2 强烈推荐的模板其实是 while (left < right)。每一步探索一个mid，如果mid可能是答案，那么把mid保留在下一次搜索区间，否则把mid排除出下一次搜索区间。
这样退出的时候必有left==right。如果这题有解，那么收敛解一定就是最终解，不用double check你的结果。
的确我也很喜欢while (left < right)，因为最后返回的收敛解就是left = right = mid，尽量（绝对）不要用while (left <= right)，因为你根本不清楚到底该返回什么值！
先上总结，然后下面从一题开始讲起，下面代码只用while (left < right)模板。
查找方式 循环条件 左侧更新 右侧更新 中间点位置 初始化
二分找左边界 left < right left = mid + 1 right = mid left + (right - left) / 2 left = 0, right = n
二分找右边界 left < right left = mid right = mid - 1 right - (right - left) / 2 left = -1, right = n - 1
找左边界/最小值，初始化为left = 0, right = n的原因是mid往左偏，所以mid的值可以覆盖[0, n)且不会越界，因为left = n - 1 时，mid = n - 1，所以下面模板结束时left = right = mid是满足condition条件的最小值/左边界。
int left = 0, right = n;
while left < right:
mid = left + (right - left) // 2
if condition(mid):
right = mid
else:
left = mid + 1
return left
找右边界/最大值，初始化为left = -1, right = n - 1的原因是mid往右偏，所以mid的值可以覆盖[0, n)且不会越界，因为left = n - 2，right = n - 1时，mid = n - 1，所以下面模板结束时left = right = mid是满足condition条件的最大值/右边界。
int left = -1, right = n - 1;
while left < right:
mid = right - (right - left) // 2
if condition(mid):
left= mid
else:
right = mid - 1
return left
记住左边界用上面模板，右边界下面模板。
Given a target integer T and an integer array A sorted in ascending order, find the index of the first occurrence of T in A or return -1 if there is no such index.
There can be duplicate elements in the array.
Examples- A = {1, 2, 3}, T = 2, return 1
- A = {1, 2, 3}, T = 4, return -1
- A = {1, 2, 2, 2, 3}, T = 2, return 1
public int firstOccur(int[] A, int target) {
if (A == null || A.length == 0) {
return -1;
}
int lo = 0;
int hi = A.length;
while (lo < hi){
int mid = lo + (hi - lo) / 2;
if(A[mid] >= target){
hi = mid;
}else{
lo = mid + 1;
}
}
return lo < A.length && A[lo] == target ? lo : -1;
}
上面程序结束时是left = right = mid 是A[mid] >= target应该插入的位置也就是满足条件A[mid] >= target的最小值
What if we want to find the index of the last occurrence of T in A or return -1 if there is no such index.
这里我们同样可以利用上一题程序选择查找插入>= target + 1的位置，然后返回的位置就是这个位置前一个
下面找到的是>= target的第一个位置，也就是正确的插入位置比如
Input: nums = [1,3,4,4,4,5,6], target = 4
Output: 4
也就寻找>= 4 + 1 = 5应该插入的位置，这里是4，也就是最后一个4的位置
因为最后返回的是--lo，所以的lo取值范围是[-1, n]，所以最后需要判断lo >= 0 && lo < n
所以如果我们需要求一个target的第一个和最后一个位置，或者=target的个数，那就可以用一个method即可
1st = lowerboud(A, target), last = lowerbound(A, target + 1) - 1, numbers = last - 1st + 1
1st = lowerboud(A, target), 1stBigger = lowerbound(A, target + 1), numbers = 1stBigger - 1st
但是注意这里只适用于整数。
public int firstOccur(int[] A, int target) {
if (A == null || A.length == 0) return -1;
int lo = 0, hi = A.length;
while (lo < hi){
int mid = lo + (hi - lo) / 2;
if(A[mid] >= target + 1){
hi = mid;
}else{
lo = mid + 1;
}
}
lo--;
return lo >= 0 && lo < A.length && A[lo] == target ? lo : -1;
}
当然直接找> target的第一个位置就更好了，是否整数都使用。但这时有重复值时下面程序会死循环，因为lo = mid
[[7,7,7],7]
注意这里因为mid = lo + (hi - lo) / 2；mid往左偏，所以条件是
if(A[mid] <= target){
lo = mid;
}
这时A[mid] = target时，lo = mid进入死循环。
public int lastOccur(int[] A, int target) {
if (A == null || A.length == 0) return -1;
int lo = 0, hi = A.length;
while (lo < hi){
int mid = lo + (hi - lo) / 2;
if(A[mid] > target){
hi = mid - 1;
}else{
lo = mid;//dead cycle
}
}
lo--;
return lo >= 0 && A[lo] == target ? lo : -1;
}
上面讨论的写法都是mid = (lo + hi) / 2或者mid = lo + (hi - lo) / 2，如果lo + 1 = hi也就是2个数挨着，那mid就偏左，所以上面把lo和hi分别初始化为0和n，没有问题，因为mid往左偏，我们只有hi = mid和lo = mid + 1，也就是mid永远不会越界。
下面mid = (lo + hi + 1) / 2或mid = hi - (hi - lo) / 2，如果lo + 1 = hi也就是2个数挨着，那mid就偏右，所以把lo和hi分别初始化为-1和n - 1，这样一定是hi = mid - 1和lo = mid，所以mid永不越界。
while left < right:
mid = right - (right - left) // 2
if condition(mid):
left= mid
else:
right = mid - 1
return left
所以上面模板结束时left = right是满足condition条件的最大值，下面就是满足A[mid] <= target的最大值
注意这里因为mid = hi - (hi - lo) / 2；mid往右偏，所以条件是
if(A[mid] <= target){
lo = mid;
}
这时A[mid] = target时，lo不断往右偏，所以不会死循环。所以找右边界建议下面程序！public int lastOccur(int[] A, int target) {
if (A == null || A.length == 0) return -1;
int lo = -1, hi = A.length - 1;
while (lo < hi){
int mid = hi - (hi - lo) / 2;
if(A[mid] > target){
hi = mid - 1;
}else{
lo = mid;
}
}
return lo >= 0 && A[lo] == target ? lo : -1;
}
当然我们也可以用这个程序去找第一个出现的值，比如
Input: nums = [1,3,4,4,4,5,6], target = 4
Output: 2
那我们只要找到<= 4 - 1 = 3的最后一个位置，那后一个位置就是结果
注意这里因为mid往右偏，而且hi = n - 1，所以lo必须初始化为-1，但是这个方法不建议使用，容易出错。public int firstOccur(int[] A, int target) {
if (A == null || A.length == 0) {
return -1;
}
int lo = -1;
int hi = A.length - 1;
while (lo < hi){
int mid = hi - (hi - lo) / 2;
if(A[mid] > target - 1){
hi = mid - 1;
}else{
lo = mid;
}
}
lo++;
return lo < A.length && A[lo] == target ? lo : -1;
}
补充内容 (2024-05-03 07:38 +08:00):
Deep Understanding of Binary Search Template
补充内容 (2024-05-07 04:00 +08:00):
当然这里可以不初始化为left = -1或right = n，只要确保left 和right覆盖解的范围即可。因为while (left < right)这个最后收敛在left = right这点上，如果left和right取的值覆盖了解的范围，那就没问题，因为最终收敛的那个解一定在left = right，而且不需要再check了。
补充内容 (2024-05-08 12:42 +08:00):
感谢网友回复，大家看看LC 162这题，这里不能初始化为right = n，原因是A[mid] 和A[mid + 1] 比较，初始化为right = n会导致mid + 1可能越界。所以初始化为left = 0, right = n - 1就对，因为解就在[0, n)。
所以初始化left 和 right的值就保证覆盖解的范围一定不会错。 |
狗仔卡
收藏
淘帖
好苗
杂草
提升卡
置顶卡
关贴卡
开贴卡
变色卡
千斤顶
楼主
