Rotated array search: identify the ordered half

Reuse ordering without reconstructing the array

A linear scan is a correct O(n) baseline using O(1) auxiliary space. Sorting a copy would lose original indices unless carried along, and it does unnecessary work. In a valid rotated array with distinct values, at most one descending break occurs between adjacent positions. For any active interval, at least one side of its midpoint is sorted. That side has an ordinary numeric range test.

Maintain the invariant that a present target lies inside the inclusive interval [lo, hi]. Check equality first. If nums[lo] <= nums[mid], the left half is sorted. Keep it only when nums[lo] <= target < nums[mid]; otherwise discard it. When the left half is not sorted, the right half is, so retain it exactly when nums[mid] < target <= nums[hi]. Distinctness makes the classification decisive. Discarding the midpoint after failed equality makes the interval shrink. An empty interval proves absence, not merely failure to guess the right pivot.

The core loop is O(log(n+1)) time and O(1) auxiliary space. The public reference validates in O(n), making end-to-end time O(n), with constant auxiliary space. For n > 1, count descending edges including the wraparound edge: a valid strict rotation has exactly one descent and no equal adjacent circular values. Cutting at that descent yields a strictly increasing sequence, proving the validation rule sufficient. An unrotated sequence's descent is its wrap edge.

Follow-up 1: duplicates become legal

Predict the ambiguity for midpoint equality. Two arrays can show the same left, middle, and right values while hiding the smaller target on opposite sides.

After checking equality, when all three boundary values are equal, discard one element at each end and continue. Correctness survives but worst-case time becomes O(n). Define whether any matching index or the first exported index is required; the original early return does not enforce a first-index tie rule.

Follow-up 2: many queries share an immutable rotation

Store the pivot and search logical value nums[(p+i) % n]; no sorted copy is necessary if the underlying array remains stable. A senior candidate defends the half-range comparisons and tests every rotation of small arrays. A lead candidate defines immutable snapshot lifetime and rejects claims of logarithmic worst-case search after allowing arbitrary duplicates or unvalidated updates.

Run and check

From the repository root:

cd curriculum/01-code/02-data-structures-algorithms/problems/12-rotated-array-search
python -m unittest -v test_solution.py

Reference implementation (download file, source below) · Contract and oracle tests (download file, source below). Read the tests after your attempt. A green reference suite verifies the supplied implementation; it does not demonstrate independent transfer. Reimplement one follow-up with the reference closed and explain which old invariant no longer holds.

def _integers(values):
    if not isinstance(values, (list, tuple)) or any(type(x) is not int for x in values):
        raise ValueError("expected a list or tuple of integers, excluding bool")

def rotated_search(nums, target):
    _integers(nums)
    if type(target) is not int:
        raise ValueError("target must be an integer")
    n = len(nums)
    if n > 1:
        descents = 0
        for i in range(n):
            current, following = nums[i], nums[(i + 1) % n]
            if current == following:
                raise ValueError("values must be distinct")
            descents += current > following
        if descents != 1:
            raise ValueError("input must be a strict sorted rotation")
    lo, hi = 0, n - 1
    while lo <= hi:
        mid = lo + (hi - lo) // 2
        if nums[mid] == target:
            return mid
        if nums[lo] <= nums[mid]:
            if nums[lo] <= target < nums[mid]:
                hi = mid - 1
            else:
                lo = mid + 1
        elif nums[mid] < target <= nums[hi]:
            lo = mid + 1
        else:
            hi = mid - 1
    return -1

import itertools
import unittest
from solution import rotated_search

class RotationTests(unittest.TestCase):
    def test_contract(self):
        self.assertEqual(rotated_search([4, 5, 7, 0, 1, 2], 1), 4)
        self.assertEqual(rotated_search([], 6), -1)
        self.assertEqual(rotated_search([1], 1), 0)
        for nums in [[2, 1, 3], [1, 1], [2, 1, 2], [True], [1, 3, 2, 4]]:
            with self.assertRaises(ValueError):
                rotated_search(nums, 1)

    def test_every_rotation_against_linear_lookup(self):
        for n in range(7):
            for ordered in itertools.combinations(range(-3, 4), n):
                for pivot in range(max(1, n)):
                    nums = ordered[pivot:] + ordered[:pivot]
                    for target in range(-4, 5):
                        expected = nums.index(target) if target in nums else -1
                        self.assertEqual(rotated_search(nums, target), expected)

if __name__ == "__main__":
    unittest.main()