关于二分查找及其变体的一些个人理解

概要

二分查找可谓是日常开发中最常用的几种算法之一，在C++用我们可以使用STL标准模板库中提供的算法，例如lower_bound, upper_bound等函数，但用其他语言开发时可就没那么好的待遇了，掌握二分查找及其变体的写法是很有必要的

有一篇文章讲解二分的变体，讲解的很好，文章用一个基础代码框架配合一个表格（表格记录了每种变体与基础代码框架的不同之处）来描述了所有二分查找的变体，本文就不赘述了，附上链接:

https://blog.csdn.net/ylyg050518/article/details/78825577

上面文章中提到的二分查找的变体的【比较符及返回值表格】不太好记忆

但是如果知道如何推导这个表格，那就更好的记住它，也就掌握了二分的所有变体

我用Python写了一遍，写上了详细的注释，描述了每种变体使用的比较符和返回值的意义，写篇文章记录一下。

---

最基础的二分查找如下

返回有序数组array中值和target相等的成员的下标，如果不存在，返回-1

# 这段基础二分查找的代码也是其他变体的框架，其他变体都是在这段代码上做少量的改动
def binary_search(array, target):
    # 初始化操作
    count = len(array)
    left = 0
    right = count - 1

    # 最外层的while循环使用的比较符是<=，否则不能返回正确结果
    # 其他变体也同样使用<=，很统一，很好记
    # 如果使用【<】比较符，在数组长度为1函数会直接返回-1，因为（ left==right）
    while(left <= right):
        # 如果使用表达式 mid = (left + right) / 2 来计算的话
        # 在 left + right 很大时容易溢出
        mid = math.floor(left + (right - left) / 2)   
        if(array[mid] == target):
            return mid
        # 因为外层while循环使用了【<=】比较符，所以跳转时：
        # 要么left = mid + 1，要么是 right = mid - 1, 不能是 left = mid 或 right = mid
        # 因为mid的计算时向下取整的，有可能导致mid一直等于left而死循环！
        if(array[mid] < target):
            left = mid + 1
        elif(array[mid] > target):
            right = mid - 1
           
    # 找不到目标 
    return -1

---

二分查找变体（只写一种作为示例）

查找有序数组array中值与target相等的成员的下标，如果不存在，返回-1

def find_last_less_equal(array, target):

    count = len(array)
    left = 0
    right = count - 1

    while(left <= right):
        mid = math.floor(left + (right - left) / 2) 
        # 因为要查的是last_less_equal
        # 当array[mid] < target 时：
        #   - 因为我们要查的目标是小于等于target的，而array是有序数组
        #   - 所以如果结果存在，一定是mid右侧的某一个成员
        #   - 所以结果不可能在mid左侧，此时，执行left = mid + 1
        # 当array[mid] == target 时：
        #   - 因为数组中可能有多个与targe相同的数，我们要找的是last
        #   - 所以结果要么是mid，要么是mid右侧的某一个成员
        #   - 所以结果不可能在mid左侧，此时，执行left = mid + 1
        # 当array[mid] > target 时：
        #   - 因为我们要查的目标是小于等于target的，而array是有序数组
        #   - 所以如果结果存在，一定是mid左侧的某一个成员
        #   - 所以结果不可能在mid右侧，此时，执行right= mid - 1
        # 所以在array[mid] < target 和 array[mid] == target 时，得让left = mid + 1
        # 即在本二分变体中，下面这行代码使用的比较符是【 <= 】，其他变体都用这个思路确定if语句中的比较符
        if(array[mid] <= target):
            left = mid + 1
        else:
            right = mid -1
        # 每次跳转后，原先的mid就在搜索区域(left-right)外了
        # 如果这个mid就是目标结果，会不会导致结果被忽略？
        # 答案是不会，这是因为循环使用的比较符是while(left <= right)
        # 所以循环结束时，要么是left = right + 1，要么是 right = left - 1
        # 如果这个mid就是目标结果，最终还是能停在它身上！

    # 我们发现，
    # 查last的过程中，当mid可能是结果时，结果也可能存在于mid右侧
    # 所以一直无法排除right就是我们要查的目标的嫌疑，所以查last的变体都返回right
    # 同理
    # 查first的过程中，当mid可能是结果时，结果也可能存在于mid左侧
    # 所以一直无法排除left就是我们要查的目标的嫌疑，所以查first的变体都返回left
    # ------
    # 总结：
    # 其他二分变体都用这个思路确定返回值
    # ------
    # 另外，right只会减，left只会加
    # 所以循环结束时
    # 如果返回的是right, right要么是目标idx, 要么一直减少直到 right等于-1
    # 如果返回的是left, right要么是目标idx, 要么一直增加直到 left等于数组总长
    return right

---

总结（根据上面例子推导其他变体）

返回值的确定：

• 查last的过程中，当mid可能是结果时，结果也可能存在于mid右侧，一直无法排除right就是我们要查的目标的嫌疑，所以查last的变体都返回right
• 查first的过程中，当mid可能是结果时，结果也可能存在于mid左侧，一直无法排除left就是我们要查的目标的嫌疑，所以查first的变体都返回left。

比较符的确定：

下面这个表格无需记忆，脑子里思考一下就可以推导出来
（推导过程参考上面变体代码中的注释）

变体	array[mid] < target	array[mid] == target	array[mid] > target
last_less	left 右跳	right 左跳	right 左跳
last_less_equal	left 右跳	left 右跳	right 左跳
last_equal	left 右跳	left 右跳	right 左跳
first_greater	left 右跳	left 右跳	right 左跳
first_greater_equal	left 右跳	right 左跳	right 左跳
first_equal	left 右跳	right 左跳	right 左跳

由上表可以推导出：

• last_less 函数在 array[mid] < target 时，应该left跳，否则right跳
• last_less_equal 函数在 array[mid] <= target 时，应该left跳，否则right跳
• last_equal 函数在 array[mid] <= target 时，应该left跳，否则right跳
• first_greater 函数在 array[mid] <= target 时，应该left跳，否则right跳
• first_greater_equal函数在 array[mid] < target 时，应该left跳，否则right跳
• first_equal函数在 array[mid] < target 时，应该left跳，否则right跳

最终推导出文章开头提到的【比较符及返回值表格】

变体	符号	返回值
last_less	<	right
last_less_equal	<=	right
last_equal	<=	right
first_greater	<=	left
first_greater_equal	<	left
first_equal	<	left