Generated by Codex with GPT-5

Quick facts

What the problem is really asking

The array started out sorted in ascending order, then got rotated at some pivot.

That means a sequence like [0, 1, 2, 4, 5, 6, 7] might become [4, 5, 6, 7, 0, 1, 2].

The task is to find the index of a target value in O(log n) time, not just to tell whether it exists.

So the real challenge is this:

how can binary search still work when the array is no longer globally sorted from left to right?

The key insight

Even after rotation, the whole array is not random. At any midpoint, at least one half is still normally sorted.

For example, if the midpoint lands in the left sorted block, then the left half is ordered. If it lands in the right sorted block, then the right half is ordered.

That is enough to keep discarding half of the search space:

  • determine which half is sorted
  • check whether the target could live inside that sorted half
  • keep that half if it can, otherwise discard it and search the other half

Because the problem guarantees distinct values, these comparisons are unambiguous.

How to derive the optimal solution

Ordinary binary search works because a sorted array lets each midpoint split the world cleanly into “too small” and “too large”.

Rotation breaks that global ordering, but it does not break local ordering everywhere. One side of the midpoint is always ordered.

Suppose the current search range is left ... right and the midpoint is mid.

If numbers[left] <= numbers[mid], then the left half is sorted.

  • if numbers[left] <= target < numbers[mid], the target must be in that left half
  • otherwise it must be in the other half

If that condition is false, then the right half is sorted.

  • if numbers[mid] < target <= numbers[right], the target must be in that right half
  • otherwise it must be in the left half

This preserves the same logarithmic shrinking as standard binary search:

  • Time: O(log n)
  • Extra space: O(1)

Best approaches

The cleanest approach is a one-pass modified binary search. It finds the answer directly without first locating the pivot.

There is also a two-phase version:

  1. find the rotation pivot with binary search
  2. run a second binary search in the correct sorted half

That is also O(log n), but the one-pass method is shorter and usually easier to explain in an interview.

Python solution

from typing import List


class Solution:
    def search(self, numbers: List[int], target: int) -> int:
        left_index = 0
        right_index = len(numbers) - 1

        while left_index <= right_index:
            middle_index = (left_index + right_index) // 2
            middle_value = numbers[middle_index]

            if middle_value == target:
                return middle_index

            # One side of the current range must still be in sorted order.
            if self._left_half_is_sorted(numbers, left_index, middle_index):
                if self._target_is_in_left_half(
                    numbers,
                    left_index,
                    middle_index,
                    target,
                ):
                    right_index = middle_index - 1
                else:
                    left_index = middle_index + 1
            else:
                if self._target_is_in_right_half(
                    numbers,
                    middle_index,
                    right_index,
                    target,
                ):
                    left_index = middle_index + 1
                else:
                    right_index = middle_index - 1

        return -1

    def _left_half_is_sorted(
        self,
        numbers: List[int],
        left_index: int,
        middle_index: int,
    ) -> bool:
        return numbers[left_index] <= numbers[middle_index]

    def _target_is_in_left_half(
        self,
        numbers: List[int],
        left_index: int,
        middle_index: int,
        target: int,
    ) -> bool:
        return numbers[left_index] <= target < numbers[middle_index]

    def _target_is_in_right_half(
        self,
        numbers: List[int],
        middle_index: int,
        right_index: int,
        target: int,
    ) -> bool:
        # The endpoints are inclusive, but the midpoint was already checked.
        return numbers[middle_index] < target <= numbers[right_index]

The takeaway

The important pattern is not “rotated array” by itself. The important pattern is:

binary search can still work when full ordering is broken, as long as each step reveals one side that is ordered enough to reason about.

Once that idea clicks, the rest of the solution becomes a small extension of ordinary binary search rather than a completely different technique.