“Binary search”的版本间的差异
跳到导航
跳到搜索
（→变化） |
|||
| 第21行： | 第21行： | ||
== 变化 == | == 变化 == | ||
| − | <code>mid</code> 赋值为 <code>floor(left + right) / 2</code> 时，需要用 <code>left = mid + 1</code> 和 <code>right = mid</code>，循环判断为 <code>left < right</code> <ref>https://github.com/CyC2018/CS-Notes/blob/master/notes/Leetcode%20%E9%A2%98%E8%A7%A3%20-%20%E4%BA%8C%E5%88%86%E6%9F%A5%E6%89%BE.md</ref> | + | <code>mid</code> 赋值为 <code>floor((left + right) / 2)</code> 时，需要用 <code>left = mid + 1</code> 和 <code>right = mid</code>，循环判断为 <code>left < right</code> <ref>https://github.com/CyC2018/CS-Notes/blob/master/notes/Leetcode%20%E9%A2%98%E8%A7%A3%20-%20%E4%BA%8C%E5%88%86%E6%9F%A5%E6%89%BE.md</ref> |
=== 合并大于和等于的情况 === | === 合并大于和等于的情况 === | ||
2021年11月4日 (四) 23:30的版本
二分法。
一般 pattern
low = 0
high = n
while low <= high:
mid = (low + high) // 2
mid_calc = f(mid)
if mid_calc == target:
return g(mid)
elif mid_calc < target:
low = mid + 1
else:
high = mid - 1
return default_retval
注意 low <= high, low = mid + 1 和 high = mid - 1。
变化
mid 赋值为 floor((left + right) / 2) 时，需要用 left = mid + 1 和 right = mid，循环判断为 left < right [1]
合并大于和等于的情况
如需找到元素第一次出现的下标（Leetcode 34. Find First and Last Position of Element in Sorted Array），可将 mid_calc 等于和大于的情况合并，并给新的 high 赋值时不 + 1。
C++ 示例：[2]
int lower_bound(vector<int> &nums, int target) {
int low = 0;
int high = nums.size();
int mid;
while (low < high) {
mid = low + (high - low) / 2;
if (nums[mid] >= target) {
high = mid;
} else {
low = mid + 1;
}
}
return low;
}