我正在做面试准备问题，并遇到了这个问题： Search an element in a sorted and rotated array.
对我来说最明显的解决方案是 1) 找到枢轴点（其中数字大于下一个数字），并且 2) 使用它作为分割点来知道旋转和排序数组的哪一半执行二进制搜索 .
我找到了一个"better"（或者他们在极客中声称是极客）解决方案 . 为了不让你厌烦代码，这里是高层次的想法 . 我的问题是： I don't understand how finding the middle point let's us search in only one pass. 这真的比我提出的最初解决方案更好吗？
高水平的“改进/更好”方法：
1) Find middle point mid = (l + h)/2
2) If key is present at middle point, return mid.
3) Else If arr[l..mid] is sorted
a) If key to be searched lies in range from arr[l]
to arr[mid], recur for arr[l..mid].
b) Else recur for arr[mid+1..r]
4) Else (arr[mid+1..r] must be sorted)
a) If key to be searched lies in range from arr[mid+1]
to arr[r], recur for arr[mid+1..r].
b) Else recur for arr[l..mid]
1 回答
您的第1步要求您找到枢轴点 . 要做到这一点，需要搜索 . 该解决方案结合了对枢轴点的二进制搜索和对目标的二进制搜索;你的解决方案没有 .