“Binary search”的版本间的差异
跳到导航
跳到搜索
（建立内容为“二分法。 一般 pattern： <syntaxhighlight lang=python> low = 0 high = n while low <= high: mid = (low + high) // 2 mid_calc = f(mid) if mid_cal…”的新页面） |
|||
| 第1行： | 第1行： | ||
二分法。 | 二分法。 | ||
| − | 一般 | + | == 一般 pattern == |
<syntaxhighlight lang=python> | <syntaxhighlight lang=python> | ||
low = 0 | low = 0 | ||
| 第18行： | 第18行： | ||
注意 <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>。 | ||
| + | |||
| + | == 变化 == | ||
| + | |||
| + | === 合并大于和等于的情况 === | ||
| + | |||
| + | 如需找到元素第一次出现的下标（[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:双指针]] | ||
2021年6月17日 (四) 19:13的版本
二分法。
一般 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。
变化
合并大于和等于的情况
如需找到元素第一次出现的下标（Leetcode 34. Find First and Last Position of Element in Sorted Array），可将 mid_calc 等于和大于的情况合并，并给新的 high 赋值时不 + 1。
C++ 示例：[1]
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;
}