.png)
Find Minimum in Rotated Sorted Array
Problem Statement
You are given a rotated sorted array of unique integers.
The array was originally sorted in ascending order and then rotated at some pivot unknown to you.
Your task is to find the minimum element in the array.
Example 1
Input
arr = [3, 4, 5, 1, 2]
Output
1
Example 2
Input
arr = [4, 5, 6, 7, 0, 1, 2]
Output
0
Example 3
Input
arr = [11, 13, 15, 17]
Output
11
Why This Problem Is Important
- Classic binary search interview question
- Tests understanding of sorted + rotated arrays
- Improves problem-solving with search space reduction
- Foundation for rotation-based problems
- Frequently asked by FAANG companies
Key Observations
- Array is sorted but rotated
- There is only one point where order breaks
- Minimum element is the pivot
- Binary search can find it in O(log n)
Approach 1: Linear Scan
Idea
Traverse the array and keep track of the minimum value.
Algorithm
- Initialize minVal = arr[0]
- Traverse the array
- Update minVal whenever a smaller element is found
- Return minVal
Time & Space Complexity
- Time: O(n)
- Space: O(1)
Approach 2: Binary Search (Optimal)
Idea
In a rotated sorted array:
- One half is always sorted
- The minimum lies in the unsorted half
Algorithm
Initialize:
low = 0 high = n - 1- While low < high:
- Find mid
If arr[mid] > arr[high]
→ Minimum lies in the right halflow = mid + 1Else
→ Minimum lies in the left half (including mid)high = mid
- Return arr[low]
Time & Space Complexity
- Time: O(log n)
- Space: O(1)
Implementations
C
#include
int main() {
int arr[] = {4, 5, 6, 7, 0, 1, 2};
int n = 7;
int low = 0, high = n - 1;
while (low < high) {
int mid = low + (high - low) / 2;
if (arr[mid] > arr[high])
low = mid + 1;
else
high = mid;
}
printf("%d", arr[low]);
return 0;
}
C++
#include
using namespace std;
int main() {
int arr[] = {4, 5, 6, 7, 0, 1, 2};
int n = 7;
int low = 0, high = n - 1;
while (low < high) {
int mid = low + (high - low) / 2;
if (arr[mid] > arr[high])
low = mid + 1;
else
high = mid;
}
cout << arr[low];
return 0;
}
Java
public class FindMinimumInRotatedArray {
public static void main(String[] args) {
int[] arr = {4, 5, 6, 7, 0, 1, 2};
int low = 0, high = arr.length - 1;
while (low < high) {
int mid = low + (high - low) / 2;
if (arr[mid] > arr[high])
low = mid + 1;
else
high = mid;
}
System.out.print(arr[low]);
}
}
Python
arr = [4, 5, 6, 7, 0, 1, 2]
low, high = 0, len(arr) - 1
while low < high:
mid = (low + high) // 2
if arr[mid] > arr[high]:
low = mid + 1
else:
high = mid
print(arr[low])
JavaScript
let arr = [4, 5, 6, 7, 0, 1, 2];
let low = 0, high = arr.length - 1;
while (low < high) {
let mid = Math.floor((low + high) / 2);
if (arr[mid] > arr[high])
low = mid + 1;
else
high = mid;
}
console.log("Minimum element =", arr[low]);
Dry Run
Input:
[4, 5, 6, 7, 0, 1, 2]
| low | mid | high | arr[mid] | arr[high] | Action |
|---|---|---|---|---|---|
| 0 | 3 | 6 | 7 | 2 | low = mid + 1 |
| 4 | 5 | 6 | 1 | 2 | high = mid |
| 4 | 4 | 5 | 0 | 1 | high = mid |
| 4 | 4 | 4 | — | — | Stop |
Minimum Element:
0
Summary
- Rotated sorted array always has one pivot
- Linear scan works but is inefficient
- Binary search reduces time to O(log n)
- Interview-preferred optimal solution
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
