Find Minimum in Rotated Sorted Array

Problem Description

You are given a rotated version of a sorted array. The original array was sorted in ascending order and then rotated between 1 and n times.

Your task is to find the minimum element in the array.

Constraints:

• All elements are unique.

• The array was originally sorted in ascending order.

• You must solve the problem in O(log n) time.

What is a Rotated Sorted Array?

A rotated sorted array means a part of the array has been shifted to the end or beginning.

Example:
Original array: [0, 1, 2, 4, 5, 6, 7]
Rotated 4 times → [4, 5, 6, 7, 0, 1, 2]

Notice that the array is still made of two sorted parts. Your goal is to find the smallest number, which is also the point of rotation.

Example

Input: nums = [3, 4, 5, 1, 2]
Output: 1
Explanation: The array was originally [1, 2, 3, 4, 5] and rotated 3 times. The smallest number is 1.

Solution Overview

Since the array is partially sorted, the best way to find the minimum value in O(log n) time is by using Binary Search.

We compare the middle element with the rightmost element:

• If the middle element is greater than the rightmost, then the smallest value is in the right half.

• Otherwise, it’s in the left half or could be the middle element itself.

C++ Code

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

        while (left < right) {
            int mid = (left + right) / 2;
            if (nums[mid] > nums[right]) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }

        return nums[left];
    }
};

Notes

• This approach guarantees O(log n) time due to binary search.

• It’s frequently asked in technical interviews, especially at Meta.