T42 两个有序序列的共同中位数

类似快速排序思想,每次比较两个序列的中位数,根据大小关系缩小查找范围,直到找到共同中位数。

  • 若 P1 的中位数大于 P2 的中位数,则共同中位数在 P1 的左半部分和 P2 的右半部分。
  • 若 P1 的中位数小于 P2 的中位数,则共同中位数在 P1 的右半部分和 P2 的左半部分。
  • 递归进行上述过程,直到两个序列的长度为 1 或 2, 直接计算中位数。