Search in Rotated Sorted Array

题目

Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.

(i.e., [0,1,2,4,5,6,7] might become [4,5,6,7,0,1,2]).

You are given a target value to search. If found in the array return its index, otherwise return -1.

You may assume no duplicate exists in the array.

Your algorithm’s runtime complexity must be in the order of O(log n).

Example 1:

Input: nums = [4,5,6,7,0,1,2], target = 0
Output: 4
Example 2:

Input: nums = [4,5,6,7,0,1,2], target = 3
Output: -1
           

分析

1.不管在那个点旋转，数组中总有一半是有序的

2.找到有序的一半，并判断target是否在其中，如果在，则在有序的一半中继续查找，否则在另一半查找

3.画图分析

黑色为数组的值，从图中我们可以看出，当nums[low] < nums[mid]的，low-mid一定是有序的，当nums[low] > nums[mid]时，mid-high一定是有序的

4.分析边界条件，假设我们使用mid=(low + high) // 2，当nums[low]=nums[mid]

1）考虑只有一个数的情况，直接用nums[mid] == target就能判断出结果

2）考虑两个数的情况，比如【1，2】或【4，1】。这种情况我们希望我们的算法能对这两个数都判断一遍，因为我们无法确定他们的大小关系。所以先对low判断，再对high判断。发现可以把这一类归类到nums[low] < nums[mid]的情况。

代码：

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        lo, hi = 0, len(nums) - 1
        while lo <= hi:
            mid = (lo + hi) // 2
            if nums[mid] == target:
                return mid
            
            if nums[mid] >= nums[lo]: # lo-mid is ordered
                if nums[lo] <= target <= nums[mid]:
                    hi = mid - 1
                else:
                    lo = mid + 1
            else: # mid-hi is ordered
                if nums[mid] <= target <= nums[hi]:
                    lo = mid + 1
                else:
                    hi = mid - 1
                
        return -1