我认为这是对子数组A[0..n-1]和的两个并发二进制搜索B[0..n-1]，即O（log n）。

• 给定排序数组，您知道 第n个 最大数组将出现A[n-1]在array 之前或之后的某个位置A，或者B[n-1]是否在array中B
• 考虑索引a中的A项目和索引b中的项目B。
• 如下执行二进制搜索（相当粗糙的伪代码，不考虑“一次性”问题）：
  • 如果为a + b > n，则减少搜索集
  • 如果是的A[a] > B[b]话b = b / 2，否则a = a / 2
  • 如果为a + b < n，则增加搜索集
  • 如果A[a] > B[b]那么b = 3/2 * b，其他a = 3/2 * a（中途之间a和以前a）
  • 如果a + b = n那么第 n 大是max(A[a], B[b])

我相信最坏的情况是O（ln n），但无论如何肯定是亚线性的。