## Search in Rotated Sorted Array

###### DESCRIPTION (credit Leetcode.com)

You are given a sorted array that has been rotated at an unknown pivot point, along with a target value. Develop an algorithm to locate the index of the target value in the array. If the target is not present, return -1. The algorithm should have a time complexity of O(log n).

Note:

- The array was originally sorted in ascending order before being rotated.
- The rotation could be at any index, including 0 (no rotation).
- You may assume there are no duplicate elements in the array.

###### EXAMPLES

**Example 1**:

Input:

`nums = [4,5,6,7,0,1,2], target = 0`

Output: 4 (The index of 0 in the array)

**Example 2**:

Input:

`nums = [4,5,6,7,0,1,2], target = 3`

Output: -1 (3 is not in the array)

Run your code to see results here

## Explanation

The fact that this question is asking for a O(log n) solution is a hint that we should be using **binary search** to solve it. If we can iteratively search for our target value in the array while reducing the relevant search space by half in each iteration, then we can achieve the desired time complexity.

So let's first look at an example of a rotated sorted array and see if we can notice anything that will help us do so.

#### Reducing the Search Space

The visual below shows the same sorted array rotated at different points, including no rotation at all.

If we draw a line down the middle element of each array, this splits the array into two halves. Notice how **at least one of the halves is always sorted in ascending order**, shown in dark green in the visual.

The fact that one half of the array is always sorted is great for our goal, **because we can quickly tell if our target falls within the range of that half** by comparing the target with its endpoints.

If our target 3 falls within the range of the sorted half, we can confidently discard the other half of the array:

Otherwise, we can discard the sorted half and continue our search in the other half.

So we've accomplished our goal - we used the fact the one half of the array is always sorted to reduce our search space by half.

We can now apply the same logic as above to the half of the array we didn't discard. But first, let's see how to determine which half of the array is sorted.

#### Determining the Sorted Half

In a regular, unrotated, sorted array, the first element will always be less (or equal to) the middle element. However, this isn't always true for a rotated sorted array.

In a rotated search array, the middle element mid will sometimes be less than the first element left. This happens when the rotation occurs somewhere between left and mid, meaning the right half of the array is sorted.

However, if the middle element mid is greater than the first element left, we know that the left half of the array is sorted, like shown in the 3 examples below.

### Algorithm

We now have enough information to visualize our algorithm.

Initialize two pointers left = 0 and right = len(nums) - 1 as the boundaries of our search space.

Now we iteratively try to reduce our search space until its either empty or we find the target.

- Initialize pointer mid = (left + right) // 2, and check if nums[mid] == target. If we find the target, we return mid. If it isn't, this removes mid from our search space.

**Determine which half is sorted**: check if nums[left] < nums[mid]. If true, the left half is sorted. If not, the right half is sorted.

In this case, the left half is sorted, so we check if the target is within nums[left] (8) and nums[mid] (16).

3 is not within 8 and 16, so we discard the left half of the array from our search space by updating left = mid + 1. We just reduced our search space in half!

Now we repeat the process as above with the updated search space...

- Set mid = (left + right) // 2 and check if nums[mid] == target.

**Check which half is sorted**: nums[left] (17) is greater than nums[mid] (1), so the**right half is sorted**.**Check if the target is within nums[mid] (1) and nums[right] (3)**. It is, so we update left = mid + 1 to discard the left half of the array.

This continues until either we find the target or our search space is empty (left > right).

## Solution

def search(nums, target):left = 0right = len(nums) - 1while left <= right:mid = (left + right) // 2if nums[mid] == target:return midif nums[left] <= nums[mid]:# left half is sortedif nums[left] <= target and target < nums[mid]:# target is in the left halfright = mid - 1else:# target is in the right halfleft = mid + 1else:# right half is sortedif nums[mid] < target and target <= nums[right]:# target is in the right halfleft = mid + 1else:# target is in the left halfright = mid - 1return -1

def search(nums, target):left = 0right = len(nums) - 1while left <= right:mid = (left + right) // 2if nums[mid] == target:return midif nums[left] <= nums[mid]:if nums[left] <= target and target < nums[mid]:right = mid - 1else:left = mid + 1else:if nums[mid] < target and target <= nums[right]:left = mid + 1else:right = mid - 1return -1

## Complexity Analysis

**Time Complexity:** O(log n). We are reducing the search space by half in each iteration, just like we do in classic binary search.

**Space Complexity:** O(1). We are using a constant amount of space.

Loading comments...