这可以通过O(logN)使用稍微修改的二进制搜索来完成。

排序+旋转数组的有趣特性是，将数组分为两半时，将始终对这两个半数中的至少一个进行排序。

Let input array arr = [4,5,6,7,8,9,1,2,3]
number of elements  = 9
mid index = (0+8)/2 = 4

[4,5,6,7,8,9,1,2,3]
         ^
 left   mid  right

好像右子数组未排序而左子数组已排序。

如果中点恰好是旋转点，则将对左右两个子数组进行排序。

[6,7,8,9,1,2,3,4,5]
         ^

但是 无论如何都必须对一半（子数组）进行排序 。

通过比较每半的开始和结束元素，我们可以很容易地知道哪半被排序。

一旦找到排序的哪一半，我们就可以看到该一半中是否存在密钥-与极端情况进行简单比较。

如果键在那一半中存在，我们将在另一半上递归调用函数，而
在另一半中递归调用搜索。

我们在每次调用中都丢弃了一半的数组，从而产生了这种算法O(logN)。

伪代码：

function search( arr[], key, low, high)

        mid = (low + high) / 2

        // key not present
        if(low > high)
                return -1

        // key found
        if(arr[mid] == key)
                return mid

        // if left half is sorted.
        if(arr[low] <= arr[mid])

                // if key is present in left half.
                if (arr[low] <= key && arr[mid] >= key) 
                        return search(arr,key,low,mid-1)

                // if key is not present in left half..search right half.
                else                 
                        return search(arr,key,mid+1,high)
                end-if

        // if right half is sorted. 
        else    
                // if key is present in right half.
                if(arr[mid] <= key && arr[high] >= key) 
                        return search(arr,key,mid+1,high)

                // if key is not present in right half..search in left half.
                else
                        return search(arr,key,low,mid-1)
                end-if
        end-if

end-function

这里的关键是将始终对一个子数组进行排序，使用该子数组可以丢弃数组的一半。