基于二分查找左右索引的两个有序数组中位数求解疑问

给定两个长度分别为l和m的有序数组A和B，合并后数组长度n=l+m，需求解合并数组的中位数。根据中位数定义，它大于一半元素且小于另一半元素。若A[i]是中位数，因A有序，A[i]≥A[0..i-1]，同时需大于B中j=⌈n/2⌉-(i-1)个元素，即A[i]≥B[0..j-1]。若A[i]不是中位数，可通过A[i]与B[j]、B[j+1]的大小关系判断其与中位数的大小，进而进行二分查找。

相关伪代码如下：

MEDIAN-SEARCH(A[1 . . l], B[1 . . m], left,right)

if left > right:
  MEDIAN-SEARCH(B, A, max(1, ⌈n/2⌉ − l), min(m, ⌈n/2⌉))

i = ⌊(left + right)/2⌋

j = ⌈n/2⌉ - i

if (j = 0 or A[i] > B[j]) and (j = m or A[i] <= B[j + 1])
  return A[i]

else if (j = 0 or A[i] > B[j]) and j != m and A[i] > B[j + 1]
  return MEDIAN-SEARCH(A, B, left, i − 1)

else
  return MEDIAN-SEARCH(A, B, i + 1, right)

初始调用为：

MEDIAN-SEARCH(A[1..l], B[1..m], max(1, ⌈n/2⌉ − m), min(l, ⌈n/2⌉))

疑问1：初始调用中left和right取值的作用 #

初始调用里的left和right是给二分查找划定有效候选区间，直接排除掉A中不可能是中位数的位置，避免做无用功。

拆解一下两个值的逻辑：

• ⌈n/2⌉是合并后数组里，中位数及之前的元素总个数（比如n=5时是3，前3个元素包含中位数；n=4时是2，对应中位数相关的计数逻辑）。
• min(l, ⌈n/2⌉)：就算B的所有元素都比A小，A里前⌈n/2⌉个元素才可能包含中位数，超过这个位置的元素肯定比中位数大，完全不用查。
• max(1, ⌈n/2⌉ − m)：如果B的所有元素都比A大，那A至少要拿出⌈n/2⌉ - m个元素，才能凑够合并数组前⌈n/2⌉个元素（B最多贡献m个）。所以A中比这个位置靠前的元素，肯定比中位数小，也不用查。

说白了，这俩值把A里可能是中位数的位置框死在一个小范围里，让二分查找从一开始就精准定位，减少递归次数。

疑问2：算法的时间复杂度是O(log(N))还是O(log(max(l,m)))？ #

严格来说，这个算法的时间复杂度是O(log(min(l,m)))，但如果要在你给出的两个选项里选，它更接近O(log(max(l,m)))，实际效率比O(log(N))更高。

原因是：每次递归都会把当前处理数组的查找范围减半；当其中一个数组的候选范围耗尽（left>right），算法会切换到另一个数组继续二分。最终的递归次数由两个数组中较短的那个长度决定——比如A长1000，B长10，切换后在B上最多递归4次（log₂(10)≈3.32），远小于log₂(1010)≈10（也就是O(log(N))的情况）。

如果两个数组长度接近，比如l=m，那log(min(l,m))=log(max(l,m))=log(N/2)≈log(N)，这时候三个复杂度表述的差异可以忽略，但本质上还是由较短数组的长度主导。

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