找到旋转的下标 rotation_index ，也就是数组中最小的元素。二分查找在这里可以派上用场。找到rotation_index之后，如果 target > nums[0] 则说明targe在rotation_index 前面，否在target肯定在rotation_index 后面，在选中的数组区域中再次使用二分查找。

题目

假设按照升序排序的数组在预先未知的某个点上进行了旋转。
( 例如，数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。
搜索一个给定的目标值，如果数组中存在这个目标值，则返回它的索引，否则返回 -1 。
你可以假设数组中不存在重复的元素。
你的算法时间复杂度必须是 O(log n) 级别。

示例

示例 1:

输入: nums = [4,5,6,7,0,1,2], target = 0
输出: 4

示例 2:

输入: nums = [4,5,6,7,0,1,2], target = 3
输出: -1

考察知识点

数组、二分查找

核心思想

算法非常直接：

• 找到旋转的下标 rotation_index ，也就是数组中最小的元素。二分查找在这里可以派上用场。

1.png

• 找到rotation_index之后，如果 target > nums[0] 则说明targe在rotation_index 前面，否在target肯定在rotation_index 后面，在选中的数组区域中再次使用二分查找。

代码步骤

1、定义find_rotate_index内部函数，利用二分查找确定
1.1、特判：nums[left] < nums[right]这种情况就是没有翻转，rotate_index==0。
1.2、不断循环，知道找到降序出现的位置，计算中值。rotate_index这个位置刚好出现降序，满足条件的话，就返回pivot + 1即可。
1.3、否则，调整二分查找区间。如果当前节点值小于left对应值，则设置right为当前节点-1。否则设置left为当前节点+1。
2、定义内部二分查找函数search
2.1、计算mid，如果mid对应值等于待查找值，直接返回mid。否则，调整二分查找区间，继续查找。待查找值小于中值，更新right。反之，更新left。查找不到，返回-1。
3、主程序部分，根据长度进行几次特判，长度为0，长度为1。
3.1、找到rotate_index
3.2、根据rotate_index与target、0、nums[0]的关系，设置二分查找的区间。
改进版本：一趟搞定，旋转后，一边符合升序，一边不符合，利用此特点，见题解评论。

LeetCode题解

Python版本

代码实现

class Solution:
    def search(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: int
        """
        # 定义find_rotate_index内部函数，利用二分查找确定rotate_index，rotate_index这个位置刚好出现降序。
        def find_rotate_index(left, right):
            if nums[left] < nums[right]:  # 特判：nums[left] < nums[right]这种情况就是没有翻转，rotate_index==0。
                return 0

            while left <= right:  # 不断循环，知道找到降序出现的位置
                pivot = (left + right) // 2  # 计算中值
                if nums[pivot] > nums[pivot + 1]:  # rotate_index这个位置刚好出现降序，满足条件的话，就返回pivot + 1即可。
                    return pivot + 1
                else:  # 否则，调整二分查找区间。
                    if nums[pivot] < nums[left]:  # 如果当前节点值小于left对应值，则设置right为当前节点-1。
                        right = pivot - 1
                    else:  # 否则设置left为当前节点+1
                        left = pivot + 1
        
        # 定义内部二分查找函数search
        def search(left, right):
            """
            Binary search
            """
            while left <= right:
                pivot = (left + right) // 2  # 计算mid
                if nums[pivot] == target:  # 如果mid对应值等于待查找值，直接返回mid。
                    return pivot
                else:  # 否则，调整二分查找区间，继续查找。
                    if nums[pivot] > target:  # 待查找值小于中值，更新right。
                        right = pivot - 1
                    else:  # 反之，更新left。
                        left = pivot + 1
            return -1  # 查找不到，返回-1。
        
        # 根据长度进行几次特判，长度为0，长度为1
        n = len(nums)
        if n == 0:
            return -1
        if n == 1:
            return 0 if nums[0] == target else -1 

        # 找到rotate_index
        rotate_index = find_rotate_index(0, n - 1)
        
        # 根据rotate_index与target、0、nums[0]的关系，设置二分查找的区间。
        # if target is the smallest element
        if nums[rotate_index] == target:
            return rotate_index
        # if array is not rotated, search in the entire array
        if rotate_index == 0:
            return search(0, n - 1)
        if target < nums[0]:
            # search on the right side
            return search(rotate_index, n - 1)
        # search on the left side
        return search(0, rotate_index)


print("leet code accept!!!")
Input = [[4,5,6,7,0,1,2], [4,5,6,7,0,1,2]]
Input1 = [0, 3]
    for i in range(len(Input)):
Answer = [4, -1]

if __name__ == "__main__":
    solution = Solution()
        print("-"*50)
        result = solution.search(Input[i], Input1[i])
        print(result==Answer[i])

时间复杂度 \(O(logN)\)
空间复杂度 \(O(1)\)