Back to DSA
Find Minimum in Rotated Sorted Array
mediumA sorted array of distinct values has been rotated some number of times. Locate the smallest element in O(log n) time.
Examples
Example 1:
Input:
nums = [6,7,8,1,2,3]Output:
1Explanation: The rotation point is at value 1.
Example 2:
Input:
nums = [2,3,4,5,1]Output:
1Explanation: The array was rotated so that 1 ended up at the last position.
Hints
class Solution {
public int findMin(int[] nums) {
int lo = 0, hi = nums.length - 1;
while (lo < hi) {
int mid = lo + (hi - lo) / 2;
if (nums[mid] > nums[hi]) lo = mid + 1;
else hi = mid;
}
return nums[lo];
}
}Time complexity
O(log n)Space complexity
O(1)