Search in Rotated Sorted Array Visualizer & Step-by-Step Algorithm Solution

Find target index in a rotated sorted array in O(log n) time by finding the pivot (minimum element) and binary searching the target segment.

Category: binary-search | Difficulty: Medium

Tags: Binary Search, Rotated Array, Two Phase

Search in Rotated Sorted Array

nums (Rotated)
LEFT
4
0
5
1
6
2
7
3
0
4
1
5
RIGHT
2
6
100%
state
target0
phaseInit
left0
right6
resultSearching
Initialization
1/14
Explanation

Start search for target = 0 in rotated sorted array of length 7.

Source Code
1function search(nums, target) {
2 let left = 0, right = nums.length - 1;
3 // Phase 1: Find pivot (minimum index)
4 while (left < right) {
5 const mid = Math.floor((left + right) / 2);
6 if (nums[mid] < nums[right]) right = mid;
7 else left = mid + 1;
8 }
9 const minIdx = left;
10 // Phase 2: Select subarray
11 if (target >= nums[minIdx] && target <= nums[nums.length - 1]) {
12 left = minIdx; right = nums.length - 1;
13 } else {
14 left = 0; right = minIdx - 1;
15 }
16 // Phase 3: Binary search
17 while (left <= right) {
18 const mid = Math.floor((left + right) / 2);
19 if (nums[mid] === target) return mid;
20 else if (nums[mid] < target) left = mid + 1;
21 else right = mid - 1;
22 }
23 return -1;
24}