Search in Rotated Sorted Array

Problem Id: 33 Difficulty: Medium Tag: Array Tag: Binary Search


Intuition

Divide the array into 2 parts left and right. Since this array is rotated sorted, elements in left is always bigger than elements in right.

Let's choose the middle of this array. The middle element should be either in left or in right. If mid is in left, then it must be greater than max(right) = right[-1], and we could simply judge whether the target is in its left or right. And if mid is in right, it must be smaller than right[-1]. And we could also simply judge whether the target is in its right.

Solution


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

            if nums[lo] <= nums[mid]:
                if nums[lo] <= target < nums[mid]:
                    hi = mid - 1
                else:
                    lo = mid + 1
            else:
                if nums[mid] < target <= nums[hi]:
                    lo = mid + 1
                else:
                    hi = mid - 1
        return -1