Pratice here

Suppose an array of length n sorted in ascending order is rotated between 1 and n times.

Notice that rotating an array [a[0], a[1], a[2], ..., a[n-1]] 1 time results in the array [a[n-1], a[0], a[1], a[2], ..., a[n-2]].

Given the sorted rotated array nums of unique elements, return the minimum element of this array.

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

Brute Force#

A linear scan works because the minimum element exists somewhere in the array — we just don't know where. Traverse every element once, keeping track of the smallest value seen so far. This ignores the sorted structure entirely, making it simple but suboptimal.

class Solution {
public:
    int findMin(vector<int>& nums) {
        int mini = INT_MAX;

        for(int i=0;i<nums.size();i++){
            mini = min(mini, nums[i]);
        }
        return mini;
    }
};

Time Complexity: O(n)

Space Complexity: O(1)

Better Approach: Binary Search#

Use binary search to find the minimum in O(log n) time by identifying the sorted halves of the array and narrowing the search space.

• In a rotated sorted array, at least one half is always sorted.
• The minimum element always lies in the unsorted half or at the boundary of the sorted part.

class Solution {
public:
    int findMin(vector<int>& nums) {
        int n = nums.size();

        int s = 0, e = n-1;
        int mini = INT_MAX;

        while(s<=e)
        {
            int mid = s + (e-s)/2;

            if(nums[s] <= nums[mid]) //left half sorted
            {
                mini = min(nums[s], mini);
                s = mid+1;
            }else{
                mini = min(nums[mid], mini);
                e = mid-1;
            }
        }
        return mini;
    }
};

Time Complexity: O(log n)

Space Complexity: O(1)

Summary#