Problem
Given an integer array nums that was originally sorted in ascending order and then possibly rotated, return the minimum element in the array.You may assume that all elements in the array are distinct. The algorithm should run in
O(log n) time.
Example(s)
Consider the following example(s) to understand the expected input and output.Input
nums = [3,4,5,1,2] Output
1 Solution
This solution uses a modified Binary Search. In a rotated sorted array, the minimum element is the point where the sorted order changes.We compare the middle element with the rightmost element. If
nums[mid] > nums[right], the minimum must be to the right of mid. Otherwise, mid may be the minimum, so the search continues in the left half.
The search space is repeatedly reduced by half until
left and right meet. That position contains the minimum element.
public int findMin(int[] nums) {
int left = 0;
int right = nums.length - 1;
while (left < right) {
int mid = left + (right - left) / 2;
if (nums[mid] > nums[right]) {
left = mid + 1;
} else {
right = mid;
}
}
return nums[left];
}
Complexity
Each iteration eliminates half of the remaining search space, resulting in a time complexity ofO(log n). The algorithm uses only a few variables, so the extra space complexity is O(1).