数值数组中的二分查找：递归实现有序数组首个≥N的最左元素索引定位

这个需求和普通二分查找的核心区别是，哪怕在中间位置已经找到满足≥目标值的元素，也不能立刻返回——因为输入数组是升序排列的，左侧可能还有索引更小、值同样满足要求的元素，必须继续收缩搜索范围到左半区，直到找到最靠左的匹配位置。

递归逻辑设计 #

• 递归函数需要维护两个动态边界值：当前搜索区间的左起点low、右终点high，加上固定的原输入数组arr和待查找目标值N
• 初始启动递归时，搜索范围覆盖整个数组：low=0，high = len(arr) - 1
• 基础终止条件：当low > high时，代表整个区间已经搜索完毕，此时low的值就是最终要返回的最左索引（如果目标值比数组所有元素都大，返回值会等于数组长度，符合越界的语义）
• 每次递归先计算区间内的中间位置mid，推荐用mid = low + (high - low) // 2的写法，避免直接写(low+high)//2可能带来的整数溢出问题
• 如果当前中间位置的元素满足arr[mid] >= N：说明这个位置的元素符合要求，但左侧区域可能存在索引更小的同值元素，因此把搜索的右边界收缩到mid -1，在左半区间继续递归查找
• 如果当前中间位置的元素满足arr[mid] < N：说明当前位置及整个左半区间的元素都小于目标值，不可能出现符合要求的位置，因此把搜索的左边界收缩到mid +1，在右半区间继续递归查找

代码实现（Python） #

def find_leftmost(arr, target):
    # 内部递归函数，对用户隐藏动态边界参数
    def search(low, high):
        # 递归终止
        if low > high:
            return low
        mid = low + (high - low) // 2
        if arr[mid] >= target:
            # 当前元素满足要求，继续向左搜索更靠左的位置
            return search(low, mid - 1)
        else:
            # 当前元素小于目标，向右半区搜索
            return search(mid + 1, high)
    # 初始搜索范围为整个数组
    return search(0, len(arr) - 1)

验证测试 #

参考给定示例数组调用：

test_arr = [1, 3, 3, 4, 5, 7, 11, 11, 12, 15]
print(find_leftmost(test_arr, 11))

运行输出为6，和预期结果完全匹配。

常见踩坑点 #

• 最容易出错的逻辑是碰到arr[mid] >= N时就直接返回mid，这样会命中遍历路径上第一个碰到的匹配值，而不是全局最左的位置——比如示例中如果碰到索引7的11就提前返回，结果会错成7
• 不要把终止条件设为low == high，那样会漏掉最后一个边界的判断，导致返回值出现1个位置的偏差

内容的提问来源于stack exchange，提问作者smunteanu