# Leetcode 33 Solution

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
``````