Pra*_*ora 7 sorting algorithm complexity-theory
我遇到了以下问题:
假设我修改了4n个不同数字的给定排序列表,如下所示:
将元素保持在偶数位置(位置2,4,6,... 4n).在奇数编号的位置上形成n个不相交的对(i,j),其中对于某些k = 0到n-1,i = 2k + 1,对于某些k = n到2n-1,j = 2k + 1.
现在交换位置i和j中的元素用于每个这样的对.(即,数组前半部分奇数编号位置的每个元素与数组后半部分奇数编号位置的某个元素交换.多个交换中不涉及任何元素(即交换是不相交的)你不知道这些(i,j)对,除了在数组的前半部分中奇数编号位置的元素与后半部分中奇数编号位置的某个元素交换.现在给出一个元素x,解释如何在O(logn)时间内确定x是否在(new reshu ffl ed)数组中.
老实说,我不知道如何处理这个问题.给定x,我可以使用二分搜索搜索它是否存在于任何偶数位置.但奇数位置的数字不再排序.
任何帮助表示赞赏.谢谢!
您可以x通过执行两次二进制搜索来确定某个元素是否在新(混洗)集中.这里的关键是奇数元素基本上充当彼此的"键",因为它们已经以不相交的对交换.
使用标准二进制搜索进行查找x,确保始终选择偶数索引进行比较.(使用偶数索引是至关重要的,因为那些元素仍然是有序的.)
如果x数组在偶数索引处,则会找到它.如果没有,我们最终会找到两个元素m,并n使得m < x < n和index(n) - index(m) == 2.这意味着如果阵列仍然排序,x将必须在元件之间m和n(如果它是在阵列中).
考虑在m和之间的索引处的元素n- 调用它y.如果element x在原始数组中,则必须y在创建shuffled数组时交换它.
执行第二次二进制搜索以查找y,再次确保您只选择偶数索引进行比较.同样第2步,你最终会找到两个元素m',并n'使得m' < y < n'和index(n') - index(m') == 2.如果阵列仍然排序,元素y会之间的元素m'和n'.
m'和之间的元素n'必须是交换的元素y,因此最初在m和之间的元素n.如果此值不是x,则x数组中不存在.