Search in Rotated Sorted Array

Find a target in a sorted array that was rotated once.

Start with the concrete trace below. It shows the state the algorithm must carry as it runs.

Problem trace

Search in Rotated Sorted Array: Keep the interval containing target 0 by identifying one sorted half at each probe.

Input and goalFind a target in a sorted array that was rotated once.

Use the sorted left halfleft=0, right=6, and middle=3. Since nums[0]=4 <= nums[3]=7, indices 0..3 are sorted; target 0 is not in [4,7), so set left=4.

left405162middle730415right26

target0sortedindices 0..3decision0 not in [4, 7): left = 4

Recognize it

The array was sorted and rotated once with distinct values, so although the whole interval may cross the pivot, at least one side of middle remains sorted.

Keep true

If target 0 exists, it remains in inclusive [left, right]. A half is discarded only after its sorted value range proves whether target can occur there.

Reuse it

When a monotone ordering is disrupted once, find a locally ordered region and use its endpoint values to make the same safe-elimination argument as ordinary binary search.

Pattern: Binary search with one sorted half.

Simple idea: At least one half around the middle is sorted. Find that half. If the target fits inside its values, search it. Otherwise search the other half.

def search_rotated(nums: list[int], target: int) -> int:
   left, right = 0, len(nums) - 1

   while left <= right:
      middle = (left + right) // 2
      if nums[middle] == target:
         return middle

      if nums[left] <= nums[middle]:
         if nums[left] <= target < nums[middle]:
            right = middle - 1
         else:
            left = middle + 1
      elif nums[middle] < target <= nums[right]:
         left = middle + 1
      else:
         right = middle - 1

   return -1

Cost: $O(\log n)$ time and $O(1)$ space.