šŸ‘Øā€šŸ’» 738LeetCode

Search in Rotated Sorted Array

Question

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. Assume no duplicates. Require runtime in the order of O(logN).

Example

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

Solution

Binary Search.
In the given example, there are seven ways to rotate the array, as shown below. The bold part means a sorted part.

0怀怀1怀怀2怀怀 4怀怀5怀怀6怀怀7

7怀怀0怀怀1怀怀 2怀怀4怀怀5怀怀6

6怀怀7怀怀0怀怀 1怀怀2怀怀4怀怀5

5怀怀6怀怀7怀怀 0怀怀1怀怀2怀怀4

4怀怀5怀怀6怀怀7怀怀0怀怀1怀怀2

2怀怀4怀怀5怀怀6怀怀7怀怀0怀怀1

1怀怀2怀怀4怀怀5怀怀6怀怀7怀怀0

The key question here is how to know whether to continue searching in the left part or in the right part. We notice the bold part is always sorted. This means we can compare the middle number with the rightmost number to know if this is the bold part. If mid < right, then the right part is sorted. Otherwise, the left part is sorted, so this is how we differentiate these two cases.

The next step is to check if the target is in this sorted range. If so, we limit the range and keep searching in this range in the next loop. If not, we limit the range to the other part and continue searching. The loop is terminated until the target is found.

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        if not nums:
            return -1
        left, right = 0, len(nums) - 1
        while left <= right:    # Use "<=" instead of "="
            mid = right + (right - left) >> 1
            if nums[mid] == target:
                return mid
            elif nums[mid] < nums[right]:
                if nums[left] <= target <= nums[mid]:    # left is sorted
                    right = mid - 1
                else:                                    # right is sorted
                    left = mid + 1
            else:
                if nums[mid] <= target <= nums[right]:   # right is sorted
                    left = mid + 1
                else:                                    # left is sorted
                    right = mid - 1
        return -1