在 log(n) 时间内搜索元素
Searching for an element in log(n) time
我遇到了以下问题：
Suppose I modify a given sorted list of 4n distinct numbers as follows:
Keep elements in even positions (positions 2, 4, 6, ... 4n) as they are. Form n disjoint pairs (i,j) on the odd numbered positions where i = 2k+1 for some k = 0 to n−1 and j = 2k+1 for some k = n to 2n−1.
Now swap elements in positions i and j for every such pair. (i.e. every element in an odd numbered position in the first half of the array is swapped with some element in an odd numbered position in the second half of the array. No element is involved in more than one swap (i.e. the swaps are disjoint). You don’t know these (i,j) pairs except that an element in an odd numbered position in the first half of the array is swapped with some element in an odd numbered position in the second half. Now given an element x, explain how you can determine whether or not x is in the (new reshuffled) array in O(logn) time.
老实说，我不确定如何处理这个问题。给定 x，我可以使用二进制搜索来搜索它是否存在于任何偶数位置。但是奇数位置的数字不再排序
感谢任何帮助。谢谢！
您可以通过进行两次二进制搜索来确定某个元素 x 是否在新的（打乱的）集合中。这里的关键是奇数元素本质上彼此充当 "keys"，因为它们已经以不相交的对交换。
使用标准的二进制搜索来查找 x，确保您始终选择 even 索引进行比较。 （使用偶数索引是至关重要的，因为这些元素仍然是有序的。）
如果x在数组中的偶数索引处，它会被找到。如果不是，我们最终会找到两个元素 m 和 n 使得 m < x < n 和 index(n) - index(m) == 2。这意味着如果数组仍然排序，x 必须是 m 和 n 之间的元素（如果它在数组中）。
考虑 m 和 n 之间索引处的元素 - 称其为 y。如果元素 x 在原始数组中，则在创建打乱后的数组时，它必须已与 y 交换。
执行第二次二进制搜索以查找 y，再次确保您只选择 even 索引进行比较。与步骤 2 类似，您最终会找到两个元素 m' 和 n'，使得 m' < y < n' 和 index(n') - index(m') == 2。如果数组仍然排序，元素 y 将是 m' 和 n' 之间的元素。
m' 和 n' 之间的元素必须是与 y 交换的元素，因此任何元素最初是在 m 和 n' 之间n。如果这个值不是x，那么数组中不存在x。
我遇到了以下问题：
Suppose I modify a given sorted list of 4n distinct numbers as follows:
Keep elements in even positions (positions 2, 4, 6, ... 4n) as they are. Form n disjoint pairs (i,j) on the odd numbered positions where i = 2k+1 for some k = 0 to n−1 and j = 2k+1 for some k = n to 2n−1.
Now swap elements in positions i and j for every such pair. (i.e. every element in an odd numbered position in the first half of the array is swapped with some element in an odd numbered position in the second half of the array. No element is involved in more than one swap (i.e. the swaps are disjoint). You don’t know these (i,j) pairs except that an element in an odd numbered position in the first half of the array is swapped with some element in an odd numbered position in the second half. Now given an element x, explain how you can determine whether or not x is in the (new reshuffled) array in O(logn) time.
老实说，我不确定如何处理这个问题。给定 x，我可以使用二进制搜索来搜索它是否存在于任何偶数位置。但是奇数位置的数字不再排序
感谢任何帮助。谢谢！
您可以通过进行两次二进制搜索来确定某个元素 x 是否在新的（打乱的）集合中。这里的关键是奇数元素本质上彼此充当 "keys"，因为它们已经以不相交的对交换。
使用标准的二进制搜索来查找
x，确保您始终选择 even 索引进行比较。 （使用偶数索引是至关重要的，因为这些元素仍然是有序的。）如果
x在数组中的偶数索引处，它会被找到。如果不是，我们最终会找到两个元素m和n使得m < x < n和index(n) - index(m) == 2。这意味着如果数组仍然排序，x必须是m和n之间的元素（如果它在数组中）。考虑
m和n之间索引处的元素 - 称其为y。如果元素x在原始数组中，则在创建打乱后的数组时，它必须已与y交换。执行第二次二进制搜索以查找
y，再次确保您只选择 even 索引进行比较。与步骤 2 类似，您最终会找到两个元素m'和n'，使得m' < y < n'和index(n') - index(m') == 2。如果数组仍然排序，元素y将是m'和n'之间的元素。m'和n'之间的元素必须是与y交换的元素，因此任何元素最初是在m和n'之间n。如果这个值不是x，那么数组中不存在x。