Comment on page

# 33. 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

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.

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

$array[(r - 1)] > array[r] < array[(r + 1)]$

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

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.

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.

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.

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:

if target < array[left] or target > array[right]:

left = mid + 1

else:

right = mid - 1

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:

if target < array[mid] or target > array[right]:

right = mid - 1

else:

left = mid + 1

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.Now, we can modify the standard binary search algorithm with the above logic.

class Solution:

def search(self, nums: List[int], target: int) -> int:

# [7, 8, 9, 10, 0, 1, 2, 3, 4, 5, 6]

left = 0

right = len(nums) - 1

while left <= right:

mid = (right + left) // 2

if target == nums[mid]:

return mid

elif nums[mid] > nums[right]:

# in the left side of the array

if target > nums[mid] or target < nums[left]:

# Example: [5, 6, 7, 8, 9, 0, 1, 2, 3, 4]

# Assume mid point is index 2 (value 7). We need to search to the right of the mid point for the

# cases: 1) the target is greater than the mid (i.e. target is 9) or 2) the target is less than

# the mid point but the value is actually on the right side of the array (i.e. target is 3)

left = mid + 1

else:

# This scenario is reached when we just need to search the left side of the array. This occurs when

# the target value is less than or equal to the mid point and the target is on the left side of the

# array (i.e. target is 6)

right = mid - 1

else:

# in the right side of array

if target < nums[mid] or target > nums[right]:

# Example: [5, 6, 7, 8, 9, 0, 1, 2, 3, 4]

# Assume mid point is index 8 (value 3). We need to search to the left of the mid point for the

# cases: 1) target is less than the mid (i.e. target is 0) or 2) the target is greater than the mid

# point, but the value is actually on the left side of the array (i.e. target is 6)

right = mid - 1

else:

# This scenario is reached when we need to search just the right side of the array. This occurs when

# the target value is greater or equal to the mid point value and the target is on the right side of

# the array (i.e. target 4).

left = mid + 1

return -1

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

class Solution:

def search(self, nums: List[int], target: int) -> int:

# re-implemented the iterative solution as a recursive solution.

def recurse(left, right) -> int:

if left > right:

return -1

mid = (right + left) // 2

if target == nums[mid]:

return mid

if nums[mid] > nums[right]:

if target > nums[mid] or target < nums[left]:

return recurse(mid+1, right)

else:

return recurse(left, mid - 1)

else:

if target < nums[mid] or target > nums[right]:

return recurse(left, mid - 1)

else:

return recurse(mid + 1, right)

return recurse(0, len(nums) - 1)

Last modified 1yr ago