Difficulty: Medium · LeetCode 153

Problem

Given sorted rotated array of unique elements nums, return the minimum element in $O(\log n)$ time.

Understanding the problem

The minimum element is the pivot point separating the two sorted halves.

Intuition

Compare nums[mid] against the right boundary nums[right]. If nums[mid] > nums[right], minimum lies in right half; else minimum lies in left half including mid.

Approach

Set left = 0, right = len(nums) - 1.
Loop while left < right:
Compute mid = left + (right - left) // 2.
If nums[mid] > nums[right]: minimum must be in right half left = mid + 1.
Else: minimum could be mid or to the left right = mid.
Return nums[left].

Naive Solution — Brute Force

Linear scan keeping track of minimum value.

Python

class Solution:
    def findMin(self, nums):
        answer = nums[0]

        for num in nums:
            answer = min(answer, num)

        return answer

C++

class Solution {
public:
    int findMin(vector<int>& nums) {
        int answer = nums[0];

        for (int num : nums) {
            answer = min(answer, num);
        }

        return answer;
    }
};

Java

class Solution {
    public int findMin(int[] nums) {
        int answer = nums[0];

        for (int num : nums) {
            answer = Math.min(answer, num);
        }

        return answer;
    }
}

JavaScript

var findMin = function(nums) {
    let answer = nums[0];

    for (const num of nums) {
        answer = Math.min(answer, num);
    }

    return answer;
};

Time: O(n) · Space: O(1)

Optimized Code (Python 3)

Python

class Solution:
    def findMin(self, nums):

        left = 0
        right = len(nums) - 1

        while left < right:

            mid = left + (right - left) // 2

            if nums[mid] > nums[right]:
                left = mid + 1
            else:
                right = mid

        return nums[left]

C++

class Solution {
public:
    int findMin(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];
    }
};

Java

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

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

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

        return nums[left];
    }
}

JavaScript

var findMin = function(nums) {
    let left = 0;
    let right = nums.length - 1;

    while (left < right) {
        const mid = left + Math.floor((right - left) / 2);

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

    return nums[left];
};

Time: O(log n) · Space: O(1)

Takeaway

Pattern — Rotated sorted array → Compare mid with right boundary