DSA Tracker

Visualize

Search in Rotated Sorted Array

Binary search on a rotated array

time O(log n)space O(1)

A rotated sorted array breaks plain binary search: one half of any window is ascending, the other hides the rotation cliff. But comparing nums[lo] with nums[mid] always reveals WHICH half is properly sorted, and a sorted half is decidable — either target lies inside its value range or it cannot. Discard half, repeat.

Details

Animated on: Search for target 0 in [4,5,6,7,0,1,2] — a sorted array rotated at an unknown pivot. Return its index, or -1.

Problem:Search in Rotated Sorted ArrayMedium

Pattern:Binary Search on Sorted Data

Binary search on a rotated array

step 1 / 11

4
[0]
5
[1]
6
[2]
7
[3]
0
[4]
1
[5]
2
[6]

Sorted [0,1,2,4,5,6,7] was cut after 7 and rotated. Key invariant: every window still contains at least ONE fully sorted half — that half becomes our compass.

  • lo=0· arr[0] = 4
  • hi=6· arr[6] = 2
Pseudocode
1FUNCTION search(nums, t):
2  lo = 0; hi = (the length of nums) - 1
3  WHILE lo <= hi:
4    mid = the middle index between lo and hi
5    IF nums[mid] equals t: RETURN mid
6    IF nums[lo] <= nums[mid]:   (left half is sorted)
7      IF nums[lo] <= t and t < nums[mid]: set hi to mid-1; otherwise set lo to mid+1
8    ELSE:   (right half is sorted)
9      IF nums[mid] < t and t <= nums[hi]: set lo to mid+1; otherwise set hi to mid-1
10  RETURN -1

← / → step · space play · Home restart

Every step in words

Show all 11 steps
  1. Sorted [0,1,2,4,5,6,7] was cut after 7 and rotated. Key invariant: every window still contains at least ONE fully sorted half — that half becomes our compass.
  2. mid = (0+6)/2 = 3, holding 7. Probe it against target 0.
  3. nums[3] = 7 ≠ 0 — not here yet. Decide which side can hold 0.
  4. Which half is sorted? nums[0]=4 ≤ nums[3]=7 → the LEFT half (4,5,6,7) is properly ascending. If the rotation cliff were inside lo..mid, its endpoints could not compare like this.
  5. The sorted left spans values 4..7. Target 0 < 4, so 0 cannot live there — discard indices 0..3 wholesale and jump lo to mid+1 = 4.
  6. Window shrunk to [0,1,2]. New mid = (4+6)/2 = 5, holding 1.
  7. nums[5] = 1 ≠ 0. Ask again: which half of this window is sorted?
  8. nums[4]=0 ≤ nums[5]=1 → left half of the window (values 0 and 1) is properly sorted. And notice: this window holds the rotation point's aftermath — still, exactly one clean half.
  9. Sorted-left range check: is 0 in [nums[4], nums[5]) = [0, 1)? Yes — 0 ≥ 0 and 0 < 1. Target MUST be on the left: hi = mid−1 = 4, discarding values 1 and 2 (both > 0).
  10. lo = hi = 4: one candidate left. mid = 4, nums[4] = 0 == target — return 4.
  11. Answer: 0 sits at index 4 — located in 3 probes over 7 cells. Each step identified the sorted half, proved the target outside it, and halved the window.

Now solve it yourself

Watching is the first half. The second is writing it without the animation.

Solve Search in Rotated Sorted Array in the editorAll Arrays problemsBack to roadmap