33_Search in Rotated Sorted Array

[Medium][Array, Binary Search]

Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand. (i.e.,0 1 2 4 5 6 7might become4 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.

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

Solution

Idea: Binary Search

• Since the array is rotated sorted, there must be one side that is in ascending order. Find that side and check if the target is in this side. If yes, throw away the other side. If no, throw away this side.

• The most important thing I learn from this problem is don't make the conditions for binary search too complicated. We don't need to specify each nested conditions. We can use one simple condition for one side and else for the other side.

Time Complexity: $O(\log{n})$

Space Complexity: $O(1)$

def search(nums, target):
    """
    :type nums: List[int]
    :type target: int
    :rtype: int
    """
    left, right = 0, len(nums)-1

    while left <= right:
        mid = left + (right - left)//2
        if nums[mid] == target:
            return mid
        elif nums[left] <= nums[mid]:
            # left half must be sorted
            # test if target is in left half
            if nums[left] <= target < nums[mid]:
                # keep left half
                right = mid - 1
            else:
                # keep right half
                left = mid + 1
        else:
            # right half must be sorted
            # test if target is in right half
            if nums[mid] < target <= nums[right]:
                # keep right half
                left = mid + 1
            else:
                # keep left half
                right = mid - 1
    return -1