Find Minimum in Rotated Sorted Array Visualization & Animation

Finds the minimum element in a rotated sorted array in O(log n) by comparing mid with the right boundary.

## What is it? Find the minimum element in a sorted array that has been rotated at an unknown pivot. The minimum element is the one where the rotation occurred. ## How it works - If `arr[mid] > arr[high]` → the minimum is in the right half (rotation point is to the right); move `low = mid + 1` - Else → the minimum is in the left half including `mid`; move `high = mid` - When `low == high`, that is the minimum element ## When to use - Finding the pivot/rotation point of a rotated sorted array - Used as a prerequisite step before searching in a rotated array - Any problem involving sorted arrays with a single rotation ## Key Points - Compare `arr[mid]` with `arr[high]` (not `arr[low]`) to determine which side to search - O(log n) time, O(1) space - When there are duplicates, worst case degrades to O(n)

Category: algorithms

Difficulty: intermediate

Time Complexity: O(log n)

Space Complexity: O(1)

Find Minimum in Rotated Sorted Array

intermediate

Finds the minimum element in a rotated sorted array in O(log n) by comparing mid with the right boundary.

GFGLeetCode
PhaseInit
Mid—
Min—
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
Minimum found
Active search window
Outside search space / eliminated
Find minimum in [5, 6, 7, 8, 9, 10, 1, 2, 3]. lo=0, hi=8.