Search in a Rotated Sorted Array Visualization & Animation

Searches a rotated sorted array in O(log n) by determining which half is still sorted at each step.

## What is it? Search for a target value in a sorted array that has been rotated at some unknown pivot point. Binary search still works because at least one half of the array is always sorted. ## How it works - Compute `mid = (low + high) / 2` - Determine which half is sorted: - If `arr[low] <= arr[mid]` → left half is sorted - If `target` is in `[arr[low], arr[mid])` → search left; else search right - Else → right half is sorted - If `target` is in `(arr[mid], arr[high]]` → search right; else search left - Repeat until found or `low > high` ## When to use - Searching in a rotated sorted array (LeetCode 33) - Any problem where the array has a single inflection point ## Key Points - O(log n) — binary search still applies because one half is always sorted - Handle duplicates separately — they can reduce worst case to O(n) - The key insight: at least one of the two halves is always sorted

Category: algorithms

Difficulty: intermediate

Time Complexity: O(log n)

Space Complexity: O(1)

Search in a Rotated Sorted Array

intermediate

Searches a rotated sorted array in O(log n) by determining which half is still sorted at each step.

GFGLeetCode
PhaseInit
Mid—
Result—
K =3
lo
mid
hi
↻
5
[0]
6
[1]
7
[2]
8
[3]
9
[4]
10
[5]
1
[6]
2
[7]
3
[8]
Current mid being tested
Found (K)
Active search space
Outside search space / eliminated
Search for K=3 in rotated array [5, 6, 7, 8, 9, 10, 1, 2, 3]. Rotation at index 6. lo=0, hi=8.