在O(logn)中找到合并数组中的中间元素

Question

我们有两个相同大小的排序数组n.我们称之为数组a和b.

如何找到由a和b合并的排序数组中的中间元素？

Example:

n = 4
a = [1, 2, 3, 4]
b = [3, 4, 5, 6]

merged = [1, 2, 3, 3, 4, 4, 5, 6]
mid_element = merged[(0 + merged.length - 1) / 2] = merged[3] = 3

更复杂的情况:

情况1:

a = [1, 2, 3, 4]
b = [3, 4, 5, 6]

案例2:

a = [1, 2, 3, 4, 8]
b = [3, 4, 5, 6, 7]

案例3:

a = [1, 2, 3, 4, 8]
b = [0, 4, 5, 6, 7]

案例4:

a = [1, 3, 5, 7]
b = [2, 4, 6, 8]

---

所需时间:O(log n).有任何想法吗？

Answer 1

看看两个阵列的中间部分.假设一个值较小而另一个值较大.

使用较小的值丢弃数组的下半部分.丢弃具有较高值的​​数组的上半部分.现在我们留下了我们开始时的一半.

冲洗并重复,直到每个阵列中只剩下一个元素.返回那两个中较小的一个.

如果两个中间值相同,则任意选择.

致谢:Bill Li的博客