This problem asks us to find the smallest element in an array that was originally sorted in ascending order and then rotated. The array has no duplicates.
Steps
- We use binary search to locate the minimum element efficiently.
- Initialize
l = 0andr = a.length - 1. - While
l ≤ r:- If
a[l] ≤ a[r]→ subarray is sorted → returna[l]. - Find mid:
m = l + floor((r - l) / 2) - If
a[m] < a[m - 1]→ pivot found → returna[m] - If
a[l] > a[m]→ rotation point is left →r = m - 1 - Else → rotation point is right →
l = m + 1
- If
Dry Run
Input: [3,4,5,1,2]
- l=0, r=4 → m=2 → 5 > 1 → move left → r=2
- m=1 → 4 > 5 → l=2
- m=2 → 5 > 1 → r=1
- m=0 → 3 < 4 → array sorted → return 1
Output: 1
Input: [4,5,6,70,1,2]
Output: 1
Time & Space Complexity
- Time Complexity: O(log n)
- Space Complexity: O(1)
var findMin = function(a) {
let l = 0;
let r = a.length - 1;
while (l <= r) {
if (a[l] <= a[r]) {
return a[l];
}
let m = l + Math.floor((r - l) / 2);
if (a[m] < a[m - 1]) {
return a[m];
}
if (a[l] > a[m]) {
r = m - 1;
} else {
l = m + 1;
}
}
};
int findMin(vector& a) {
int l = 0, r = a.size() - 1;
while (l <= r) {
if (a[l] <= a[r]) return a[l];
int m = l + (r - l) / 2;
if (a[m] < a[m - 1]) return a[m];
if (a[l] > a[m]) r = m - 1;
else l = m + 1;
}
return -1;
}
int findMin(int* a, int aSize) {
int l = 0, r = aSize - 1;
while (l <= r) {
if (a[l] <= a[r]) return a[l];
int m = l + (r - l) / 2;
if (m > 0 && a[m] < a[m - 1]) return a[m];
if (a[l] > a[m]) r = m - 1;
else l = m + 1;
}
return -1;
}
public class Solution {
public int findMin(int[] a) {
int l = 0, r = a.length - 1;
while (l <= r) {
if (a[l] <= a[r]) return a[l];
int m = l + (r - l) / 2;
if (m > 0 && a[m] < a[m - 1]) return a[m];
if (a[l] > a[m]) r = m - 1;
else l = m + 1;
}
return -1;
}
}
def findMin(a):
l, r = 0, len(a) - 1
while l <= r:
if a[l] <= a[r]:
return a[l]
m = l + (r - l) // 2
if m > 0 and a[m] < a[m - 1]:
return a[m]
if a[l] > a[m]:
r = m - 1
else:
l = m + 1
return -1
public class Solution {
public int FindMin(int[] a) {
int l = 0, r = a.Length - 1;
while (l <= r) {
if (a[l] <= a[r]) return a[l];
int m = l + (r - l) / 2;
if (m > 0 && a[m] < a[m - 1]) return a[m];
if (a[l] > a[m]) r = m - 1;
else l = m + 1;
}
return -1;
}
}
