[Leetcode]33. Search in Rotated Sorted Array

You are given an integer array nums sorted in ascending order, and an integer target.
Suppose that nums 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]).
If target is found in the array return its index, otherwise, return -1.

This question seems to be a complicated one, but the logic behind is quite simple if you get it in the right way. Following this post, you will see how simple and concise it is with binary search.

Logic

Defining the middle point as mid=(l+r)//2, there are only two cases:

Two cases regarding mid’s position.

In both cases, the areas split by mid could be properly extracted:

  • case i
    • mid‘s left: target<=nums[mid] and target>=nums[left]
    • mid‘s right: target > nums[mid] or target < nums[left]
  • case ii
    • mid‘s left: target<=nums[mid] or target >=nums[right]
    • mid‘s right: target>nums[mid] and target<nums[right]

Therefore, since we can concisely define left and right areas split by nums[mid], we can apply the binary search then.

Code

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

Reference

Subscribe
Notify of
guest
0 Comments
Inline Feedbacks
View all comments