Pattern visualizer
Search in Rotated Sorted Array
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. 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..
Binary search on a rotated array
time O(log n)space O(1)step 1 / 11
4
[0]5
[1]6
[2]7
[3]0
[4]1
[5]2
[6]line 2
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.
Pseudocode
1FUNCTION search(nums, t):2 lo = 0; hi = (the length of nums) - 13 WHILE lo <= hi:4 mid = the middle index between lo and hi5 IF nums[mid] equals t: RETURN mid6 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+18 ELSE: (right half is sorted)9 IF nums[mid] < t and t <= nums[hi]: set lo to mid+1; otherwise set hi to mid-110 RETURN -1
← / → step · space play · Home restart