Find Minimum in Rotated Sorted Array medium

Problem Statement

Suppose an array of length n sorted in ascending order is rotated between 1 and n times. For example, the array nums = [0,1,2,4,5,6,7] might become:

• [4,5,6,7,0,1,2] if it was rotated 4 times.
• [0,1,2,4,5,6,7] if it was rotated 0 times.

You are given a rotated sorted array nums. Return the minimum element in this array.

You must write an algorithm that runs in O(log n) time.

Example 1

• Input: nums = [3,4,5,1,2]
• Output: 1
• Explanation: The original array was [1,2,3,4,5] rotated 3 times.

Example 2

• Input: nums = [4,5,6,7,0,1,2]
• Output: 0
• Explanation: The original array was [0,1,2,4,5,6,7] rotated 4 times.

Steps

The key to solving this problem efficiently is using binary search. Since the array is rotated, the minimum element will be the only element that is smaller than its preceding element (or the first element if it's not rotated).

1. Initialization: Set left to 0 and right to nums.Length - 1.
2. Binary Search: While left < right:
   • Calculate mid as (left + right) / 2.
   • Case 1: nums[mid] > nums[right]: The minimum element is in the right half. Set left = mid + 1.
   • Case 2: nums[mid] <= nums[right]: The minimum element is in the left half (including mid). Set right = mid.
3. Return: After the loop, left and right will point to the minimum element. Return nums[left].

Explanation

The binary search efficiently narrows down the search space by half in each iteration. The condition nums[mid] > nums[right] implies that the right half contains the unsorted part of the array where the minimum element lies. Conversely, if nums[mid] <= nums[right], the minimum element is in the left half or is nums[mid] itself. This logic allows us to discard half the search space at each step, resulting in O(log n) time complexity.

Code

public class Solution {
    public int FindMin(int[] nums) {
        int left = 0;
        int right = nums.Length - 1;

        while (left < right) {
            int mid = left + (right - left) / 2; // Avoid potential overflow

            if (nums[mid] > nums[right]) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }

        return nums[left];
    }
}

Complexity

• Time Complexity: O(log n) due to the binary search.
• Space Complexity: O(1) as we use only a constant amount of extra space.