二分查找的要点就是让目标区间不断缩小直至为一个点。
这同样是一些分治算法的目标,比如快速排序,我们的目标是区间缩小为一个点,如果你不能理解这个问题,那么通常会在剩余最后两三个数的时候混乱。
我们在二分查找的时候,要不断通过left right mid的更新去达到我们最终目标;
如果我们的mid计算方式为mid = left + (right - left) / 2;
那么为了能使目标区间最终能缩小为一个点,我们在更新left的时候,至少要让left前进一步,也就是left = mid + 1。
为什么?如果更新算法是left = mid,那么当left + 1 = right;时,会进入死循环,因为相邻两个数字相加除以2得到的mid=left,这时如果更新left=mid,就会进入死循环。
而right则没有这个问题,更新right时,无论是right = mid,还是right = mid - 1,区间最终都会缩小为一个点。
如果因为题目限制,我们必须要让left=mid去更新,那么我们此时必须通过其他的mid计算方式,去避免这个问题。
我们来看两个二分查找的经典题目。
int guessNumber(int n) {
int left = 1, right = n;
while (left < right) { // 循环直至区间左右端点相同
int mid = left + (right - left) / 2; // 防止计算时溢出
if (guess(mid) <= 0) {
right = mid; // 答案在区间 [left, mid] 中
} else {
left = mid + 1; // 答案在区间 [mid+1, right] 中
}
}
// 此时有 left == right,区间缩为一个点,即为答案
return left;
}
作者:LeetCode-Solution
链接:https://leetcode.cn/problems/guess-number-higher-or-lower/solution/cai-shu-zi-da-xiao-by-leetcode-solution-qdzu/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。
int firstBadVersion(int n) {
int left = 1, right = n;
while (left < right) { // 循环直至区间左右端点相同
int mid = left + (right - left) / 2; // 防止计算时溢出
if (isBadVersion(mid)) {
right = mid; // 答案在区间 [left, mid] 中
} else {
left = mid + 1; // 答案在区间 [mid+1, right] 中
}
}
// 此时有 left == right,区间缩为一个点,即为答案
return left;
}
作者:LeetCode-Solution
链接:https://leetcode.cn/problems/first-bad-version/solution/di-yi-ge-cuo-wu-de-ban-ben-by-leetcode-s-pf8h/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。
标签:二分,right,一个点,int,mid,查找,区间,left
From: https://www.cnblogs.com/linukey/p/17417205.html