给定一个数组，例如 [7,8,9,0,1,2,3,4,5,6]，是否可以确定旋转所围绕的索引发生的速度比 O(n) 更快？
使用 O(n)，只需遍历所有元素并将第一个递减的元素标记为索引。
一个可能更好的解决方案是从两端向中间迭代，但这仍然是 O(n) 的最坏情况。
最佳答案
(编辑:下面假设元素是不同的。如果它们不是不同的，我认为没有什么比扫描数组更好的了。)
你可以二分查找。我不会发布任何代码，但这是一般的想法:(我将假设 a >= b 用于其余部分。如果 a < b ，那么我们知道它仍在排序顺序中)
取第一个元素，称之为a , 最后一个元素 b , 和中间元素，称之为 c .
如果a < c , 那么你知道枢轴在 c 之间和 b , 你可以递归(用 c 和 b 作为你的新终点)。如果a > c ，然后您知道枢轴位于两者之间的某个位置，并在该半部分递归(以 a 和 c 作为结束)。
附录:如果我们有 a = c > b，则扩展到重复的情况然后我们递归 c和 b作为我们的目的，而如果 a = c = b , 我们从 a 扫描至 c查看是否有元素 d这样它就不同了。如果不存在，则为 a 之间的所有数字和 c是相等的，因此我们递归 c和 b作为我们的目的。如果是，则有两种情况:
a > d < b :在这里，d然后是自从我们从左侧扫描以来最小的元素，我们就完成了。
a < d > b :在这里，我们知道答案介于 d 之间。和 b ，因此我们以这些为目的进行递归。
在最好的情况下，我们永远不必使用相等情况，给我们 O(log n) .最坏的情况是，这些扫描几乎涵盖了整个阵列，给我们 O(n) .
关于algorithm - 如何确定排序数组在哪个索引处旋转？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/11855709/