“Binary search”的版本间的差异
跳到导航
跳到搜索
| （未显示同一用户的3个中间版本） | |||
| 第17行： | 第17行： | ||
</syntaxhighlight> | </syntaxhighlight> | ||
| − | 注意 <code>'''low <= high'''</code>, <code>'''low = mid + 1'''</code> 和 <code>'''high = mid - 1'''</code>。 | + | 注意 <code>'''low <= high'''</code>, <code>'''low = mid + 1'''</code> 和 <code>'''high = mid - 1'''</code>。<code>while</code> 循环结束后 <code>low</code> 的值是新元素的插入位置。 |
== 变化 == | == 变化 == | ||
| + | |||
| + | <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> | ||
=== 合并大于和等于的情况 === | === 合并大于和等于的情况 === | ||
2022年1月2日 (日) 17:18的最新版本
二分法。
一般 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。while 循环结束后 low 的值是新元素的插入位置。
变化
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;
}