查看“Binary search”的源代码

二分法。

== 一般 pattern ==
<syntaxhighlight lang=python>
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
</syntaxhighlight>

注意 <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:双指针]]