Search In Rotated Sorted Array#

Problem#

A sorted array of distinct integers has been rotated at some unknown pivot, so [0, 1, 2, 4, 5, 6, 7] might become [4, 5, 6, 7, 0, 1, 2]. Given the rotated array and a target, return the index of the target, or -1 if it is absent. The solution should run in O(log n).

Example#

Array [4, 5, 6, 7, 0, 1, 2], target 0 returns 4. Target 3 returns -1.

Brute force#

A linear scan finds the target in O(n), but it throws away the structure that makes O(log n) possible.

Optimal approach#

Run a modified binary search. At each step the array splits at mid into two parts, and at least one of them is still sorted. Detect which half is sorted by comparing nums[low] to nums[mid]. If the left half is sorted and the target lies within its value range, search left, otherwise search right. Apply the mirror logic when the right half is sorted. This keeps the O(log n) halving even though the array is rotated.

Solution#

 1def search(nums: list[int], target: int) -> int:
 2    low, high = 0, len(nums) - 1
 3    while low <= high:
 4        mid = low + (high - low) // 2
 5        if nums[mid] == target:
 6            return mid
 7        if nums[low] <= nums[mid]:          # left half is sorted
 8            if nums[low] <= target < nums[mid]:
 9                high = mid - 1
10            else:
11                low = mid + 1
12        else:                                # right half is sorted
13            if nums[mid] < target <= nums[high]:
14                low = mid + 1
15            else:
16                high = mid - 1
17    return -1
18
19
20print(search([4, 5, 6, 7, 0, 1, 2], 0))  # 4
21print(search([4, 5, 6, 7, 0, 1, 2], 3))  # -1

Complexity#

• Time: O(log n), still halving each step.
• Space: O(1).

This builds on the binary search template and the broader patterns hub. Continue with the 60-day challenge.