是什么做的已经旋转的有序阵列上的二进制搜索N次的最佳方式

可能重复：
Searching a number in a rotated sorted Array 是什么做的已经旋转的有序阵列上的二进制搜索N次的最佳方式

我有一个排序的数组，它一直向右旋转N次，其中N是未知的。现在我想对它进行二分搜索。如何做呢？

eg initial array 1 4 5 8 15 

now roted N=1 time 15 1 4 5 8 
N= 2     8 15 1 4 5

N可以具有任何值，并且可以大于元素的数量。

来源

2011-02-06 algorithmX

你为什么要做这样的事情？ – jakev 2011-02-06 05:30:01

也许它是一个面试问题。一种天真低效的方法是再次使用阵列并执行二分搜索哈哈 – Enrique 2011-02-06 05:32:25

简短的答案是，你不（一次，不是在整个阵列上）。这是因为二进制搜索需要要排序的元素才能工作。

关于您可以做的最好的事情是使用二进制搜索分别搜索数组的每一半。例如，要继续上面的示例，如果N = 2，则数组将变为8 15 1 4 5。 8 15和1 4 5仍然是排序的，所以你可以二进制搜索每个子数组。在一般的意义上说，该算法因此变成：

Let your array be A, its length be M, and the target value be T. 
If (N is 0 or a multiple of M) 
    Binary search A for T 
Else 
    The sub-array A1 is the first (M mod N) elements of A. 
    The sub-array A2 is the remaining (M - (M mod N)) elements of A. 
    If (the first element of A <= T) 
     Binary search A1 for T 
    Else 
     Binary search A2 for T

可以基于A的第一元件上只搜索A1或A2中的原因是因为，如果A [0]> T，那么所有的元素根据定义，A1也将> T，因此T不能在A1中。

HTH！

编辑正如Chris在接下来的评论中指出的那样，有一种比这更简单的方法，它实际上允许您继续在整个阵列上执行二分搜索。虽然上述方法可行，但他的方法通过使用修改的比较操作巧妙地执行类似的功能，但在整个阵列上执行。

来源

2011-02-06 05:35:13 Mac

是什么做的已经旋转的有序阵列上的二进制搜索N次的最佳方式

回答

相关问题