Description

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

Solutions

  分清楚什么时候向前,什么时候向后规约即可。值得注意的是:

  1. 如果 mid 对应的数小于最右边的数的话,那么右侧就是有序的,则就着右边的进行判断,如果 target 在右侧之间,那么更新 l 指针,否则就更新 r 指针
  2. 如果 mid 对应的数大于最右边的数的话,那么左侧是有序的,如上调整两个指针
# Time: O(n)
# Space: O(1)
class Solution:
    def search(self, nums: List[int], target: int) -> int:
        if not nums or len(nums) == 0:
            return -1
        n = len(nums)
        l, r = 0, n-1
        while l <= r:
            mid = (l + r) >> 1
            if nums[mid] == target:
                return mid
            elif nums[mid] < nums[r]:
                if nums[mid] < target <= nums[r]:
                    l = mid + 1
                else:
                    r = mid - 1
            else:
                if nums[l] <= target < nums[mid]:
                    r = mid - 1
                else:
                    l = mid + 1
        return -1
# 196/196 cases passed (44 ms)
# Your runtime beats 83.98 % of python3 submissions
# Your memory usage beats 100 % of python3 submissions (12.8 MB)

  看到更快的解法,把等于号给独立出来了,其实一样,但是能减少一些计算:

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        low, high = 0, len(nums)-1
        
        while low <= high:
            mid = low + (high - low)//2
            if nums[mid] == target:
                return mid            
            if nums[low] == target:
                return low            
            if nums[high] == target:
                return high
            elif nums[mid] < nums[high]:
                if nums[mid] < target and target < nums[high]:
                    low = mid + 1
                else:
                    high = mid - 1
            else:
                if nums[low] < target and target < nums[mid]:
                    high = mid - 1
                else:
                    low = mid + 1
        
        return -1

References

  1. 33. Search in Rotated Sorted Array