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

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

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:

if target < array[mid] or target > array[right]:
    right = mid - 1
else:
    left = mid + 1

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.

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

Recursive Solution

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)

Resources

Previous20. Valid ParenthesesNext49. Group Anagrams

Last updated