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.
1#include <stdio.h>
2
3int findMin(int* nums, int numsSize) {
4 int low = 0, high = numsSize - 1;
5 while (low < high) {
6 int mid = low + (high - low) / 2;
7 if (nums[mid] > nums[high]) {
8 low = mid + 1;
9 } else {
10 high = mid;
11 }
12 }
13 return nums[low];
14}
15
16int main() {
17 int nums[] = {3, 4, 5, 1, 2};
18 int size = sizeof(nums) / sizeof(nums[0]);
19 printf("Minimum is: %d\n", findMin(nums, size));
20 return 0;
21}This C code implements a binary search algorithm to find the minimum element in a rotated sorted array. The function findMin utilizes two pointers, low and high, to define the current search space. It updates low when the middle element is greater than the element at high, indicating the rotation point is in the upper half. Otherwise, it contracts high, thereby searching in the lower half.
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.
1function findMin(nums) {
2 let min = nums[0];
3 for (const num of nums) {
4 if (num < min) {
5 min = num;
6 }
7 }
8 return min;
9}
10
11const nums = [3, 4, 5, 1, 2];
12console.log("Minimum is:", findMin(nums));The JavaScript implementation uses a linear scan to identify the smallest number in the array, updating whenever a new minimum is encountered. While this approach is foolproof for correctness, it is not efficient for large datasets.