二分查找的变体

二分查找在已经排序好的数组中寻找某个值。它是最常见的O(lgn)时间复杂度算法。

标准写法

大学教科书上只会给出一种标准写法（n是数组size，T是目标值）：

function binary_search(A, n, T) is
    L := 0
    R := n − 1
    while L ≤ R do
        m := floor((L + R) / 2)
        if A[m] < T then
            L := m + 1
        else if A[m] > T then
            R := m − 1
        else:
            return m
    return unsuccessful

循环判断条件是 <=，左右指针改变是 m + 1或者 m - 1。返回值是m。

力扣上常见的变种

力扣（LeetCode）评论区上得票最多的帖子，常常出现以下两种变种写法[1]。

寻找最左元素

function binary_search_leftmost(A, n, T):
    L := 0
    R := n
    while L < R:
        m := floor((L + R) / 2)
        if A[m] < T:
            L := m + 1
        else:
            R := m
    return L

寻找最右元素

function binary_search_rightmost(A, n, T):
    L := 0
    R := n
    while L < R:
        m := floor((L + R) / 2)
        if A[m] > T:
            R := m
        else:
            L := m + 1
    return R - 1

判断条件不是小于等于，而是严格小于。左右指针改变的时候，一边要m加一或减一，另一边却直接赋值m。返回值有时候是L，有时候是R - 1。相比最标准的写法，这两个变种真是难记，这些琐碎的细节很容易写错。

从Geeks中来，到Geeks中去

GeeksForGeeks的解法就贴近群众得多。5个变种，都由标准写法稍微改变得到[2]。

1. Contains (True or False) 包含或者不包含
2. Index of first occurrence of a key 找第一次出现
3. Index of last occurrence of a key 找最后一次出现
4. Index of least element greater than key 找第一个大于它的元素（相当于C++的upper_bound）
5. Index of greatest element less than key 找最后一个小于它的元素

只要加一个ans变量，找到一个可能的答案，还需要继续往下找时，先把这个可能的答案存在ans中。找到更合适的答案了，再次赋值给ans就行了，最后留下的就是正确答案。
判断条件始终是left <= right，边界变化始终是 mid - 1 或者 mid + 1。返回值不是mid就是ans。真好记！
我尚未验证过，但是这5个变种的2、3应该是功能相当于力扣上常见的leftmost和rightmost变种。

下面以变种2为例做一个介绍。要找从左边数起，第一个等于key的元素。90%的代码都跟标准二分查找一模一样，只有相等的case稍微改变一下——我们记下答案ans。最终返回的不是mid，是ans。这不比leftmost变种好理解又更好记吗？

int first(int low, int high, int key)
{
    int ans = -1;
 
    while (low <= high) {
        int mid = low + (high - low + 1) / 2;
        int midVal = a[mid];
 
        if (midVal < key) {
            low = mid + 1;
        }
        else if (midVal > key) {
            high = mid - 1;
        }
        else if (midVal == key) { 
            // 我们找到一个相等的元素了，但是它不一定是“最左边的”。
            // 我们记下这个可能的答案，然后移动右指针，继续往更左边找。
           // 如果没找到，那么ans就是答案。如果找到更左边的，我们会再次更新ans
            ans = mid;
            high = mid - 1;
        }
    }
 
    return ans;
}

参考资料

[1] 维基百科

[2] Geeks For Geeks