在旋转排序数组中搜索数字

给定一个可以旋转的排序数组，以最小的时间复杂度在其中找到一个元素。

例如：数组内容可以是[8,1,2,3,4,5]。假设您在其中搜索 8。

该解决方案仍然适用于二分搜索，因为您需要将数组划分为要检查的两个部分。

在排序数组中，您只需查看每个部分并确定该元素是位于第一部分（我们称之为 A）还是第二部分（B）。由于根据排序数组的定义，分区 A 和 B 将被排序，因此这仅需要对分区边界和搜索键进行一些简单的比较。

在旋转排序数组中，只能保证 A 和 B 之一是有序的。如果元素位于已排序的部分内，则解决方案很简单：只需像执行普通二分搜索一样执行搜索即可。但是，如果您必须搜索未排序的部分，则只需在未排序的部分上递归调用搜索函数即可。

这最终导致时间复杂度为O(lg n).

（实际上，我认为这样的数据结构会有一个索引来指示数组已旋转了多少个位置。）

Edit: 在 Google 上搜索后我发现this http://www.codeguru.com/forum/showthread.php?t=407535CodeGuru 上讨论同样问题的话题有些过时（但正确）。为了添加我的答案，我将复制那里给出的一些伪代码，以便它与我的解决方案一起出现在此处（思路遵循相同的思路）：

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"