Searching a rotated sorted array by finding the pivot first

$ cat the-problem.mdThe problem

We are given an array nums of distinct integers. It was sorted in ascending order and then possibly rotated: some of its numbers were moved from the front to the back, so that [0, 1, 2, 4, 5, 6, 7] might become [4, 5, 6, 7, 0, 1, 2]. Given a target, we have to return its index in nums, or $-1$ if it is not there, in $O(\log n)$ time.

Example 1

• Input: nums = [12, 15, 18, 21, 24, 3, 6, 9], target = 6
• Output: 6
• Why: the array is [3, 6, 9, 12, 15, 18, 21, 24] rotated by three places, and 6 is now at index 6.

Example 2

• Input: nums = [12, 15, 18, 21, 24, 3, 6, 9], target = 7
• Output: -1
• Why: 7 is not in the array.

Example 3

• Input: nums = [3, 6, 9, 12], target = 9
• Output: 2
• Why: this array is not rotated, and 9 is at index 2.

$ cat introduction.mdIntroduction

This problem can be broken down into three distinct parts:

1. Determine whether the array is rotatedRotated array A sorted array in which some numbers were moved from the front to the back, keeping their order. 1, 2, 3, 4, 5 rotated by two places is 3, 4, 5, 1, 2.. If it is rotated, find the pivotPivot In this article, the index of the smallest number in a rotated array. It is the one place where a number is smaller than the number before it., $p$.
2. If the array is not rotated, simply perform a binary searchBinary search A way of finding a value in a sorted array: look at the middle element, then keep only the half that can still hold the value, and repeat. on the array and return the result.
3. If the array is rotated, first perform a binary search on the left part, which is the indices $[0, p-1]$. If the target is in that part, return the result. If it is not, search the right part, which is the indices $[p, n-1]$, where $n$ is the length of nums.

From the above, we can see that once we have determined whether the array is rotated and where its pivot is, we enter one of two branches. The first branch performs a single binary search, so its time complexity is $O(\log n)$Logarithmic time The number of steps grows with the number of times the array can be halved. Doubling the array adds only one step. Written O(log n).. The second branch performs at most two binary searches, one after the other, so its time complexity is $O(\log n) + O(\log n) = O(\log n)$.

For the first part, note that if we can locate a pivot in the array, then the array must be rotated. So we do not need separate routines for determining whether the array is rotated and for finding the pivot. A single routine that finds the pivot does both.

The problem requires our solution to have a time complexity of $O(\log n)$, and we know the other parts of our solution have that time complexity. So we need to design our procedure for finding the pivot so that it also runs in $O(\log n)$ time.

$ cat approach.mdApproach

We will adapt binary search to find the pivot of a rotated array. If the array is rotated, then the pivot $p > 0$. Furthermore, if $p$ exists in an array $A$, then:

So $A$ can be divided into two regions defined by the pivot:

This uses Python’s slice notationSlice notation Python's way of naming part of a list. A[i:j] is the elements from index i up to, but not including, index j., where the left index is included and the right index is excluded.

Therefore:

• if an element $a_i \in R_0$, then $a_i \ge a_0$;
• conversely, if an element $a_i \in R_1$, then $a_i < a_0$.

Both follow from the rotation. $R_0$ is sorted and begins with $a_0$, so nothing in it is smaller than $a_0$. Every element of $R_1$ stood in front of $a_0$ before the rotation, so it is smaller than $a_0$.

$ cat deducing-the-rules-for-searching-the-array.mdDeducing the rules for searching the array

Once we note that, we can deduce our rules for searching the array:

1. Rule 1: If we have found an element $a_i \in R_0$, the pivot lies to its right, so we need to continue our search to the right of that element. That is, we must set low = mid + 1.
2. Rule 2: Similarly, if we have found an element $a_i \in R_1$ that is not the pivot, the pivot lies to its left, so we need to continue our search to the left of that element. That is, we must set high = mid - 1.

$ cat defining-the-pivot.mdDefining the pivot

Our final task is to define exactly how we know when we have found the pivot. We can define the pivot $p$ precisely by noting that it is the first element of $R_1$.

Therefore, one condition for the pivot element $a_p$ is $a_p \in R_1$, which means $a_p < a_0$. Since $a_p$ is the first element of $R_1$, the element before it is in $R_0$, which means $a_{p-1} \ge a_0$. Therefore, the second condition for the pivot is $a_{p-1} > a_p$. No other element of $R_1$ meets it: the element before any other one is also in $R_1$, which is sorted, so it is smaller.

This gives us our condition for determining whether an element is the pivot:

$ cat putting-it-together.mdPutting it together

Once we have identified what uniquely defines the pivot and determined the rules for searching the array, we have all the pieces we need to adapt binary search.

def find_pivot(nums):
    low = 0
    high = len(nums) - 1

    while low <= high:
        mid = low + (high - low) // 2
        # Is this the pivot?
        if nums[mid] < nums[0] and nums[mid - 1] > nums[mid]:
            return mid
        elif nums[mid] < nums[0]:
            # Rule 2: we are in region one, but have not found the pivot
            high = mid - 1
        else:
            # Rule 1: we must be in region zero
            low = mid + 1

    # We did not find a pivot, therefore the array is not rotated.
    # The de facto pivot is then index 0.
    return 0

When mid is 0, the first half of the pivot test, nums[mid] < nums[0], is false, so nums[mid - 1] is never read there.

$ cat try-it-yourself.mdTry it yourself

The demonstration starts with the array and target from Example 1. Each number in the array is drawn as a bar, with a line at the height of nums[0]. The bars that reach the line are in $R_0$ and the bars below it are in $R_1$. Press Step to watch the search find the pivot and then look for the target. Rotate the array by a different amount, including 0, or change the target, and step through again.

$ cat complexity.mdComplexity

• Time complexity: $O(\log n)$. Finding the pivot is one binary search, and looking for the target is at most two more.
• Space complexity: $O(1)$Constant extra space The amount of extra memory the solution uses stays the same however large the input is: a few variables, never a copy of the input. Written O(1)..

$ cat code.mdCode

class Solution:
    def search(self, nums: list[int], target: int) -> int:
        # find the pivot
        p = self.find_pivot(nums)
        if p == 0:
            return self.binary_search(nums, target, 0, len(nums) - 1)

        found = self.binary_search(nums, target, 0, p - 1)
        if found != -1:
            return found

        return self.binary_search(nums, target, p, len(nums) - 1)

    def find_pivot(self, nums):
        low = 0
        high = len(nums) - 1

        while low <= high:
            mid = low + (high - low) // 2
            if nums[mid] < nums[0] and nums[mid - 1] > nums[mid]:
                return mid
            elif nums[mid] < nums[0]:
                high = mid - 1
            else:
                low = mid + 1
        return 0

    def binary_search(self, nums, target, low, high):
        while low <= high:
            mid = low + (high - low) // 2
            if nums[mid] == target:
                return mid
            elif target < nums[mid]:
                high = mid - 1
            else:
                low = mid + 1
        return -1