查看“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>。<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 &lt; 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:双指针]]