algorithm - 在不到 O(n) 的时间内找到交换的元素？

Question

给定一个排序数组，交换两个元素，一个来自左半边，另一个来自右半边。找到交换后的元素。

答案在 O(n) 中是显而易见的，但我想知道在 O(log n) 中是否可能？

Answer 1

因为保证交换的元素来自不同的数组两半(“一个来自左半部分，另一个来自右半部分”):

1. 首先，我们可以简单地遍历数组的前半部分，在 O(n/2) = O(n)

中查找交换的元素

2. 然后我们可以使用这个交换后的元素在 O(log n/2) = O(log n)

   数组的后半部分进行二分查找/li>

因此，它仍然是 O(n) + O(log n) = O(n)，但实际上它可能比原始方法快一点。