DSA With AI
Week 2 ยท Binary Search

Search in Rotated Sorted Array

Find a target's index in a rotated sorted array, or return -1 if absent.

Medium Binary Search Week 2 Practice runner

Frame the problem

  • No duplicates in the standard version.
  • Target time is O(log n).
  • At least one side around mid is sorted.
1. Reveal example inputs and outputs

Example 1

Input:

search_rotated([
  4,
  5,
  6,
  7,
  0,
  1,
  2
], 0)

Output:

4

Example 2

Input:

search_rotated([
  4,
  5,
  6,
  7,
  0,
  1,
  2
], 3)

Output:

-1
2. Brute force first

How does normal binary search break after rotation? What sorted-side information remains true?

3. Reveal the insight ladder
  1. Compute mid.
  2. If nums[left] <= nums[mid], the left half is sorted.
  3. Check whether target lies inside that sorted half.
  4. Otherwise search the other half; mirror the logic when the right half is sorted.
4. Dry run before code
  1. nums = [4,5,6,7,0,1,2], target = 0.
  2. mid value 7 makes the left side sorted, but target is not between 4 and 7.
  3. Move right, then find 0 at index 4.
5. Reveal final Python solution 
def search_rotated(nums, target):
    left, right = 0, len(nums) - 1
    while left <= right:
        mid = (left + right) // 2
        if nums[mid] == target:
            return mid
        if nums[left] <= nums[mid]:
            if nums[left] <= target < nums[mid]:
                right = mid - 1
            else:
                left = mid + 1
        else:
            if nums[mid] < target <= nums[right]:
                left = mid + 1
            else:
                right = mid - 1
    return -1

Complexity: Time O(log n), space O(1).

Interview narration

  • Rotation does not destroy sortedness everywhere; one half remains sorted.
  • I use that half to decide whether target can be inside it.
  • Each iteration discards half the search interval.

Common traps

  • Checking target against the unsorted half.
  • Using strict comparisons that drop boundary targets.
  • Forgetting the single-element case.

Follow-up drills

1. What changes with duplicates?

When nums[left] == nums[mid] == nums[right], sorted-side detection is ambiguous; shrink both ends and accept worst-case O(n).

2. Could you find the pivot first?

Yes. Find the minimum index, then binary search the appropriate sorted segment. It is still O(log n), but usually more code.

Interactive runner

Write the required Python function. Your code runs locally in this browser. Hints reveal one failing case at a time.