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.
1public class Main {
2 public static int findMin(int[] nums) {
3 int low = 0, high = nums.length - 1;
4 while (low < high) {
5 int mid = low + (high - low) / 2;
6 if (nums[mid] > nums[high]) {
7 low = mid + 1;
8 } else {
9 high = mid;
10 }
11 }
12 return nums[low];
13 }
14
15 public static void main(String[] args) {
16 int[] nums = {3, 4, 5, 1, 2};
17 System.out.println("Minimum is: " + findMin(nums));
18 }
19}The Java solution involves a similar binary search technique to locate the minimum element of the rotated array. The findMin method narrows the search space based on the comparison of nums[mid] and nums[high], pointing inward to the side where the rotation happened.
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.
1using System;
2
3public class Solution {
4 public int FindMin(int[] nums) {
5 int min = nums[0];
6 foreach (int num in nums) {
7 if (num < min) {
8 min = num;
9 }
10 }
11 return min;
12 }
13
14 public static void Main(string[] args) {
15 int[] nums = {3, 4, 5, 1, 2};
16 Solution solution = new Solution();
17 Console.WriteLine("Minimum is: " + solution.FindMin(nums));
18 }
19}This C# code iteratively compares each element of the array with a tracked minimum element, updating the minimum accordingly. Despite its simplicity and correctness, it doesn't measure up to binary search in terms of efficiency.