转载 二分查找细节
2020-10-03 本文已影响0人
1nvad3r
总结:
- 寻找一个数:
lo = 0, hi = nums.length -1 , while (lo <= hi)
这是左闭右闭区间,只有当lo等于hi+1时,循环才会终止。
如果是while(lo < hi) 那么lo等于hi时,循环就终止了,搜索的范围会少一个数。
2.寻找一个边界:
lo = 0,hi = nums.length , while (lo < hi)
这是左闭右开区间。
最后返回lo或者hi都可以,因为循环终止的条件就是lo 等于 hi。
//初值必须覆盖解的所有可能取值
int solve(int lo, int hi) {
int mid;
while (lo < hi) {
mid = (lo + hi) / 2;
if (条件成立) {
hi = mid;
} else {
lo = mid + 1;
}
}
return lo;
}