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