# Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand. Find the minimum element in O(log N) time. You may assume the array does not contain duplicates.

By | August 22, 2024

To find the minimum element in a rotated sorted array in O(log⁡N)O(\log N)O(logN) time, you can use a modified binary search approach. The key observation is that even though the array is rotated, one part of the array will still be in sorted order. By comparing elements in the middle of the array with the start and end, you can determine which half of the array contains the minimum element.

### Steps:

1. If the middle element is greater than the last element, then the smallest element must be in the right half.
2. If the middle element is less than the last element, then the smallest element is in the left half, including the middle element itself.
3. Continue narrowing down the search space until you find the minimum element.

Here’s the implementation of this approach:

For example, given [5, 7, 10, 3, 4], return 3.

Python

``````deffind_min(nums):
left, right = 0, len(nums) - 1while left < right:
mid = (left + right) // 2# Compare middle element with the rightmost elementif nums[mid] > nums[right]:
# Minimum is in the right half
left = mid + 1else:
# Minimum is in the left half including mid
right = mid

return nums[left]

# Example usage
arr = [5, 7, 10, 3, 4]
print(find_min(arr))  # Output: 3``````

Javascript

``````functionfindMin(nums) {
let left = 0, right = nums.length - 1;

while (left < right) {
const mid = Math.floor((left + right) / 2);

// Compare middle element with the rightmost elementif (nums[mid] > nums[right]) {
// Minimum is in the right half
left = mid + 1;
} else {
// Minimum is in the left half including mid
right = mid;
}
}

return nums[left];
}

// Example usageconst arr = [5, 7, 10, 3, 4];
console.log(findMin(arr));  // Output: 3``````

Java

``````publicclassMain {
publicstaticintfindMin(int[] nums) {
intleft=0, right = nums.length - 1;

while (left < right) {
intmid= (left + right) / 2;

// Compare middle element with the rightmost elementif (nums[mid] > nums[right]) {
// Minimum is in the right half
left = mid + 1;
} else {
// Minimum is in the left half including mid
right = mid;
}
}

return nums[left];
}

publicstaticvoidmain(String[] args) {
int[] arr = {5, 7, 10, 3, 4};
System.out.println(findMin(arr));  // Output: 3
}
}``````