给定一个可以旋转的有序数组，以最小的时间复杂度在其中找到一个元素。
例如:数组内容可以是[8，1，2，3，4，5]。假设您在其中搜索8。
最佳答案
从需要将数组划分为两部分进行检查的意义上讲，该解决方案仍可用于二进制搜索。
在排序数组中，您只需查看每个部分并确定元素是位于第一部分(我们称其为A)还是第二部分(B)中。由于根据排序数组的定义，将对分区A和B进行排序，因此只需要对分区范围和搜索键进行一些简单的比较即可。
在旋转的排序数组中，只能保证对A和B中的一个进行排序。如果元素位于已排序的零件中，则解决方案很简单:只需像执行普通的二进制搜索一样执行搜索即可。但是，如果必须搜索未排序的部分，则只需递归调用未排序部分的搜索函数即可。
最终，给出了O(lg n)的时间复杂度。
(实际上，我认为这样的数据结构会附带一个索引，以指示数组已旋转了多少个位置。)
编辑:在Google上进行的搜索将我带到this，它是CodeGuru上一个过时(但正确)的话题，讨论了同样的问题。为了补充我的答案，我将复制那里给出的一些伪代码，以便它与我的解决方案一起出现在这里(思路遵循相同的思路):
Search(set):
if size of set is 1 and set[0] == item
return info on set[0]
divide the set into parts A and B
if A is sorted and the item is in the A's range
return Search(A)
if B is sorted and the item is in the B's range
return Search(B)
if A is not sorted
return Search(A)
if B is not sorted
return Search(B)
return "not found"
关于data-structures - 在旋转的排序数组中搜索数字，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/1878769/