Find Minimum in Rotated Sorted Array medium

Problem Statement

Find the minimum element in a rotated sorted array.

Suppose an array of length n is sorted in ascending order. Then it is rotated at some pivot unknown to you beforehand.

(i.e., [0,1,2,4,5,6,7] might become [4,5,6,7,0,1,2]).

Find the minimum element.

You must write an algorithm that has O(log n) time complexity.

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 to Solve

The problem can be efficiently solved using binary search. The key observation is that the minimum element is the only element that is smaller than its predecessor (if we consider the array circularly).

1. Initialize: Set left = 0 and right = nums.size() - 1.

2. Binary Search: While left < right:

   • Calculate the middle index: mid = left + (right - left) / 2 (to avoid integer overflow).
   • Case 1: nums[mid] > nums[right]: The minimum element lies in the right half. Update left = mid + 1.
   • Case 2: nums[mid] <= nums[right]: The minimum element lies in the left half (including nums[mid]). Update right = mid.

3. Return: After the loop terminates, left and right will point to the minimum element. Return nums[left].

Explanation

The algorithm works because the rotated sorted array has a unique characteristic: the minimum element is always the only element that is smaller than its right neighbor (or the last element if we consider the circular nature of rotation).

Binary search efficiently helps us narrow down the search space by comparing the middle element with the rightmost element. If the middle element is greater than the rightmost element, it means the minimum element must be in the right half (because the right half contains elements smaller than the middle). Otherwise, the minimum element is in the left half.

This approach allows us to discard half of the search space in each iteration, resulting in a logarithmic time complexity.

Code (C++)

#include <vector>
#include <algorithm>

class Solution {
public:
    int findMin(std::vector<int>& nums) {
        int left = 0;
        int right = nums.size() - 1;

        while (left < right) {
            int mid = left + (right - left) / 2;
            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 are using only a few constant extra variables.