关于O(log(m•n))复杂度的两个有序数组中位数算法的疑问

《寻找两个有序数组的中位数》是LeetCode的经典难题。O(log(min(m,n)))复杂度的实现思路相对直接，但O(log(m·n))的递归二分查找方案却容易让人困惑。这个方案的核心逻辑是：每一步确定并移除比目标元素小的那一半元素，同时把目标第k个元素的位置减去被移除元素的数量。官方说明里提到：

we can safely cut this half, and reduce k by the length of the removed half.

但实际代码实现中，看起来只减去了其中一个数组的移除长度，而非两者之和。比如这段C++代码：

if (aEnd < aStart) {
    return B[k - aStart];
}
if (bEnd < bStart) {
    return A[k - bStart];
}

数组A和B的起始索引都可能被增大（意味着对应前缀元素已被移除），但代码里只减去了其中一个索引的值，比如返回B[k - aStart]或者A[k - bStart]。很多人会疑惑：为什么这段代码能实现「每一步安全切掉一半元素，并将k减去被移除部分长度」的效果？直觉上似乎应该写成B[k-(aStart+bStart)]这样的形式，才能同时统计两个数组的移除元素数量。

要搞懂这个问题，得先明确递归过程中几个变量的核心含义：

• aStart/bStart：分别表示数组A、B中已经被确定为「比目标元素小」并被移除的元素数量（也就是A的[0, aStart-1]、B的[0, bStart-1]都已经被排除）。
• k：表示我们要找的是原始合并数组中的第k小元素（索引规则和代码保持一致，不影响核心逻辑）。

当其中一个数组耗尽（比如aEnd < aStart，说明A的所有元素都被排除了），目标元素必然在B中。此时：
原始合并数组中，已经有aStart + bStart个元素被排除（都比目标小），所以目标元素在剩余的B子数组中是第k - (aStart + bStart)小的元素。而剩余的B子数组是从bStart开始的，所以它在原始B数组中的索引就是：
bStart + (k - aStart - bStart) = k - aStart
这正好对应代码里的B[k - aStart]——本质上已经通过代数化简，把两个数组的移除数量都考虑进去了，只是看起来只减了一个值而已。

同理，当B耗尽时，目标元素在A中的原始索引是aStart + (k - aStart - bStart) = k - bStart，也就是代码里的A[k - bStart]。

另外补充一点：这个递归方案的每一步，只会从其中一个数组中移除前缀元素，不会同时操作两个数组。但即使经过多轮递归后aStart和bStart都大于0，上述的代数化简依然成立，所以代码不需要写成k-(aStart+bStart)的形式，直接用化简后的表达式即可。

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