528
个编辑
更改
无编辑摘要
二分法。
二分法。
一般 pattern：
== 一般 pattern ==
<syntaxhighlight lang=python>
<syntaxhighlight lang=python>
low = 0
low = 0
注意 <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:双指针]]