有序数组缺失元素O(log n)查找问题及函数返回值问询

嘿，这个问题我之前也纠结过返回值的问题，咱们结合逻辑和实例一步步理清楚就明白了～

首先先把核心逻辑再确认下：因为数组a和b都是有序的，且b是a去掉一个元素得到的，所以在缺失元素的左侧，a和b对应索引的元素完全一致；从缺失元素的位置开始，a的元素会比b对应索引的元素“超前”一位（相当于b从缺失位置往后的元素都左移了一位）。

二分查找的核心逻辑与返回值解惑 #

你已经理解了“中间值匹配则缺失在右侧”的逻辑，那关于返回a[l]还是a[r]的问题，关键要看二分循环的终止条件，咱们结合代码和实例来说：

具体实现思路 #

1. 初始化左指针 l = 0，右指针 r = len(a) - 1（因为a比b多一个元素，所以右边界取a的最后一个索引）
2. 循环条件设为 l < r：
   • 计算中间索引 mid = (l + r) // 2
   • 如果 a[mid] == b[mid]：说明从0到mid的元素在两个数组里完全一致，缺失元素肯定在右侧区间，所以更新 l = mid + 1
   • 如果 a[mid] != b[mid]：说明缺失元素在左侧区间（包括当前mid位置），所以更新 r = mid
3. 当循环结束时，l 和 r 会收敛到同一个位置，这个位置就是a中缺失的元素，此时返回a[l]或者a[r]都可以（因为两者指向同一个索引）

代码示例（Python） #

def find_missing(a, b):
    l, r = 0, len(a) - 1
    while l < r:
        mid = (l + r) // 2
        if a[mid] == b[mid]:
            # 前半部分完全匹配，缺失元素在右侧
            l = mid + 1
        else:
            # 出现不匹配，缺失元素在左侧或当前位置
            r = mid
    return a[l]

实例验证（彻底搞懂返回值） #

咱们拿几种典型情况测试：

• 情况1：缺失元素在中间：a = [1,2,3,4,5]，b = [1,2,4,5]
  循环过程：l=0,r=4 → mid=2，a[2]=3≠b[2]=4 → r=2；接着l=0<r=2 → mid=1，a[1]=2==b[1]=2 → l=2；此时l=r=2，返回a[2]=3，正确。
• 情况2：缺失元素在末尾：a=[1,2,3], b=[1,2]
  循环过程：l=0,r=2 → mid=1，a[1]=2==b[1]=2 → l=2；循环结束，返回a[2]=3，正确。
• 情况3：缺失元素在开头：a=[2,3,4], b=[3,4]
  循环过程：l=0,r=2 → mid=1，a[1]=3≠b[1]=4 → r=1；接着l=0<r=1 → mid=0，a[0]=2≠b[0]=3 → r=0；循环结束，返回a[0]=2，正确。

可以看到，不管缺失元素在哪个位置，循环结束时l和r都会指向它，所以返回a[l]或者a[r]结果完全一致。

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