含重复元素的二分查找问题排查：递归错误、结果错误及超时

1. RecursionError（递归深度超出限制）问题 #

• 根源：递归实现的二分查找若逻辑有误（比如每次递归仅缩小单个元素范围，导致递归深度从O(logn)退化为O(n)），或是处理超大规模数据时，递归层数会突破Python默认的递归深度限制（默认约1000层）。
• 解决：直接改用迭代实现，彻底规避递归深度问题。递归方式本身不适合处理大规模数据的二分查找，迭代是更稳妥的选择。

2. 首次出现位置结果错误问题 #

• 根源：普通二分查找找到目标值后直接返回，没有继续向左排查是否存在更早的相同元素；或是边界调整逻辑错误，比如nums[mid] == key时未收缩右边界，导致遗漏左侧的目标值。
• 解决：找到目标值时，先记录当前索引，再将右边界收缩到mid-1，继续向左搜索，直到左右边界重合。最终记录的索引就是首次出现的位置（若存在）。
• 示例代码：

def first_occurrence(nums, key):
    left = 0
    right = len(nums) - 1
    res = -1
    while left <= right:
        mid = (left + right) // 2
        if nums[mid] == key:
            res = mid
            right = mid - 1  # 继续向左找更早的出现
        elif nums[mid] < key:
            left = mid + 1
        else:
            right = mid - 1
    return res

3. 超时问题 #

• 根源：如果找到目标值后，用线性遍历向左找第一个出现位置，最坏情况下（所有元素都是目标值）时间复杂度会退化为O(n)，导致超时。
• 解决：严格遵循二分查找的O(logn)逻辑，通过调整边界持续二分搜索，而非线性遍历。上面的迭代实现始终保持O(logn)的时间复杂度，不会出现超时。

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