# 33. Search in Rotated Sorted Array

## Description

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

Note:

the input array is assumed to have at least one element

the array is sorted in ascending order and contains unique values, but is rotated at rotation point r.

the solution must run in O(log n) time.

return

`-1`

if the target value is not in the input array

## What I learned

Focus on what is known. In this case left, right and mid pointers and the values at each of those pointers.

I went down a rat hole finding the rotation point in order to solve the problem of finding the target value. But finding the rotation point adds an extra step and complexity.

## Observations

Given that the solution must run in O(log n) time points to a binary search solution.

The head element will be greater than the tail element in a rotated array. If the array is not rotated (rotation point at index 0), then the head will be less than the tail.

At the rotation point, r:

On the left side of the rotation point, all the values will be greater than the right side of the rotation point. Examples:

[2, 3, 4, 5, 0, 1]

Rotation point at index 4 (value 0). Left portion of array: [2, 3, 4, 5], right portion of array [0,1].

[1, 2, 3, 4, 5, 0]

Rotation point at index 5 (value 0). Left portion of array: [1, 2, 3, 4, 5]. Right portion of array [0]

[5, 0, 1, 2, 3, 4]

Rotation point at index 1 (value 0). Left portion of array: [5]. Right portion of array [0, 1, 2, 3, 4]

[0, 1, 2, 3, 4, 5]

Rotation point at index 0 (value 0). Right portion of array [0, 1, 2, 3, 4, 5]

## Failed Attempts at Solutions

### Attempt 1

My first thought was to find the rotation point using a binary search. If I knew the rotation point, then I could do a standard binary search on either the left or right portion of the array. If the target value was between index[0] and index[rotation - 1] then binary search the left array. Otherwise search the right array.

However, this meant I was using two binary searches. It was overly complex.

### Attempt 2

My second thought was to do one binary search on the array. I would check if `array[left] > array[right]`

. If this was true, then my range contained the rotation point. My logic for setting the left and right pointers would then take into account this fact and adjust the left and right based on this. If `array[left] < array[right]`

then I could do the normal binary search logic for setting the left and right pointers.

This logic was overly complex too. It lead to many if...else blocks and duplicated code. It is a specific solution (find solution for sorted array and find solution for unsorted array), rather than finding a generic solution that encompasses both.

## Solution

I watched Search in rotated sorted array - Leetcode 33 - Python to understand how to do this problem.

In this solution we don't worry about the rotation point. Instead we consider where in the array the mid point is located. We use the fact that `array[left] > array[right]`

for a rotated array. So if `array[mid] > array[right]`

, then mid is in the left side of the array (0..rotation point). Otherwise it is in the right side of the array (rotation point + 1...n-1).

Then we figure out whether to look to the left or right of the mid index for the target value. In the standard binary search algorithm, we do this by comparing the target value with the mid value. We need to use more complex logic for this problem.

**Left Side Logic**

**Left Side Logic**

Given an array = [ 6, 8, 10, 12, 14, 0, 2, 4], left = 0 (value 6), right = 7 (value 4), mid = 3 (value 12)

Since `array[mid] > array[right]`

(12 > 4), then mid is in the left side of the array.

In this case we use the following logic to determine how to move the left or right pointer:

target value < array[left]

Look to the right of mid pointer (move left pointer to mid + 1)

Example: if the target is 0, then we need to look to the right of the mid point. The [14, 0, 2, 4] portion of the array

target value > array[mid]

look to the right of the mid point (move left pointer to mid + 1)

Example: if target is 14, then look to right of the mid point. The [14, 0, 2, 4] portion of the array.

array[left] <= target value <= array[mid]

look to the left of mid pointer(move right pointer to mid - 1)

Example: if the target is 8, then we want to look to the left of mid point. The [6, 8, 10] portion of the array

Note: This condition is what is left over from the previous two conditions. If target value did not satisfy the first condition (

`target value < array[left]`

) then target value must be >= array[left]. And if target value did not satisfy the second condition (target value > array[mid]) then target value must be <= array[mid].

Notice in two cases that we move the left pointer to mid + 1. These can be expressed in one if statement. Here are the three cases expressed as code:

### Right Side Logic

Given the array = [ 7, 8, 1, 2, 3, 4, 5, 6], left = 0 (value 7), right = 7 (value 6), mid = 3 (value 2)

Since `array[mid] <= array[right]`

(2 < 6) the mid is in the right side of the array.

In this case we use the following logic to determine how to move the left or right pointer:

If target < array[mid]

Look to the left side of the mid point (move the right pointer to mid - 1)

Example: If target is 1, then look to the left of the mid point. The [7, 8, 1] portion on the array.

If target > array[right]

Look at the left side of the mid point (move the right pointer to mid - 1)

Example: If target is 8, then look to the left of the mid point. The [7, 8, 1] portion of the array

If array[mid] <= target <= array[right]

Look to the right side of the mid point (move the left pointer to mid + 1)

Example: If target is 5, then look to the right of the mid point. The [2, 3, 4, 5 6] portion of the array.

Note: This condition is what is left over from the previous two conditions. If target value did not satisfy the first condition (

`target value < array[mid]`

) then target value must be >= array[mid]. And if target value did not satisfy the second condition (target value > array[right]) then target value must be <= array[right].

Notice in two cases that we move the right pointer to mid - 1. These can be expressed in one if statement. Here are the three cases expressed as code:

### What about a non rotated array?

To determine whether the mid point was in the left or right side of the array, the check `array[mid] > array[right]`

is performed. Since `array[mid] <= array[right]`

in a non rotated array, the code will follow the right side logic.

For example, given the array = [1, 2, 3, 4, 5, 6], left = 0 (value 1), right = 5 (value 6), mid = 2 (value 3).

Since `array[mid] <= array[right]`

(2 < 6), the right side logic will be performed.

### Iterative Solution

Now, we can modify the standard binary search algorithm with the above logic.

### Recursive Solution

I implemented it as a recursive solution as well, just to practice recursion.

## Resources

Last updated