Leetcode 33 Solution

Leetcode Question Link

https://leetcode.com/problems/search-in-rotated-sorted-array

Thinking Process

A linear scan can definitely give us the answer to the problem, but it not interesting. Let’s try to make it O(lg N).

In this question, all we have to do is to find the first element that is greater than or equal to target. Note there is a chance no element in the array is greater than the target, in that case, we don’t care what index we return, because the final result is going to be false anyway.

We are going to follow the strategy introduced in article. We are not going to bother to think about the binary search implementation. All we care for now is to define the condition function.

If index i is the answer, we want map everything on the left to 0, and everything on the right and index i to 1.

Since the array is in the form of [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]], we’ll call [nums[k], nums[k+1], ..., nums[n-1] the left part, and nums[0], nums[1], ..., nums[k-1] the right part.

• If target is larger than to nums[-1], we know that the answer index i is on the left part. In this case, for an element j, if nums[j] >= target or nums[j] <= nums[-1], it is on the right side of i, which should be mapped to 1. Anything else should be mapped to 0.
• If target is smaller than or equal to nums[-1], we know that the answer index i is on the right part. In this case, for an element j, if target <= nums[j] <= nums[-1], it is on the right side of i, which should be mapped to 1. Anything else should be mapped to 0.

If we were to define the above rule into a single function, it should be

target > nums[-1] and (nums[j] >= target or nums[j] <= nums[-1]) \
  or target <= nums[-1] and (target <= nums[j] <= nums[-1])

Now, the only thing left is to put it into the binary_search_template defined in this article.

Time & Space Complexity

Assuming N is the size of the array:

• Time complexity: O(lg N)
• Space complexity: O(1)

Solution

class Solution(object):
    def search(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: int
        """
        if not nums:
            return -1

        l = 0
        r = len(nums) - 1

        while l < r:
            m = (l + r) // 2
            if target > nums[-1] and (nums[m] >= target or nums[m] <= nums[-1]) or target <= nums[-1] and (target <= nums[m] <= nums[-1]):
                r = m
            else:
                l = m + 1
        return l if nums[l] == target else -1