“Binary search”的版本间的差异
跳到导航
跳到搜索
（建立内容为“二分法。 一般 pattern： <syntaxhighlight lang=python> low = 0 high = n while low <= high: mid = (low + high) // 2 mid_calc = f(mid) if mid_cal…”的新页面） |
|||
| （未显示同一用户的4个中间版本） | |||
| 第1行： | 第1行： | ||
二分法。 | 二分法。 | ||
| − | 一般 | + | == 一般 pattern == |
<syntaxhighlight lang=python> | <syntaxhighlight lang=python> | ||
low = 0 | low = 0 | ||
| 第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> | ||
| + | |||
| + | === 合并大于和等于的情况 === | ||
| + | |||
| + | 如需找到元素第一次出现的下标（[https://leetcode.com/problems/find-first-and-last-position-of-element-in-sorted-array/ Leetcode 34. Find First and Last Position of Element in Sorted Array]），可将 <code>mid_calc</code> 等于和大于的情况合并，并给新的 high 赋值时不 <code>+ 1</code>。 | ||
| + | |||
| + | C++ 示例：<ref>https://github.com/changgyhub/leetcode_101</ref> | ||
| + | <syntaxhighlight lang=cpp> | ||
| + | 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; | ||
| + | } | ||
| + | </syntaxhighlight> | ||
| + | |||
| + | == 参考资料 == | ||
| + | |||
| + | <references /> | ||
[[Category:刷题]] | [[Category:刷题]] | ||
[[Category:双指针]] | [[Category:双指针]] | ||
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;
}