This approach utilizes binary search to identify the smallest element in a rotated sorted array. The idea is based on the characteristics of the rotated array where at least one half of the array is always sorted. By comparing middle and right elements, we can decide whether the rotation point lies to the left or right of the middle element, effectively narrowing down the search space.
Time Complexity: O(log n) where n is the number of elements in the input array.
Space Complexity: O(1) as no extra space is used except for variables.
1def find_min(nums):
2 low, high = 0, len(nums) - 1
3 while low < high:
4 mid = low + (high - low) // 2
5 if nums[mid] > nums[high]:
6 low = mid + 1
7 else:
8 high = mid
9 return nums[low]
10
11nums = [3, 4, 5, 1, 2]
12print("Minimum is:", find_min(nums))The Python function find_min uses pointers low and high to perform binary search and identify the smallest element in the array. It narrows the scope to the half of the array where the smallest element resides based on comparison between the mid and high elements.
This approach involves linearly iterating through the array to find the minimum value. While it doesn't meet the time complexity requirement of O(log n), it serves as a straightforward method to understand the array's properties and validate the binary search approach.
Time Complexity: O(n), as it requires traversal of the entire array in the worst-case scenario.
Space Complexity: O(1), with no additional space usage outside the input list.
1#include <stdio.h>
2
3int findMin(int* nums, int numsSize) {
4 int min = nums[0];
5 for (int i = 1; i < numsSize; i++) {
6 if (nums[i] < min) {
7 min = nums[i];
8 }
9 }
10 return min;
11}
12
13int main() {
14 int nums[] = {3, 4, 5, 1, 2};
15 int size = sizeof(nums) / sizeof(nums[0]);
16 printf("Minimum is: %d\n", findMin(nums, size));
17 return 0;
18}This C solution performs a simple iteration through the array to check each element against a minimum variable, thus directly finding the smallest number. This method ensures you check every element, although not achieving the optimal logarithmic time.