Interview Classic 150 Problem 153: Find Minimum in Rotated Sorted Array

---

Timeline

Timeline

2025-12-04

init

Divide and Conquer

---

Problem:

P153 Find Minimum in Rotated Sorted Array

https://leetcode.cn/problems/find-minimum-in-rotated-sorted-array/description/?envType=study-plan-v2&envId=top-interview-150

Similar to Find Peak Element.

#include <vector>
using std::vector;

class Solution {
    private:
        bool isLowest(vector<int> &nums, int index)
        {
                int n = nums.size();
                if (index > 0 && nums[index] < nums[index - 1]) {
                        return true;
                } else if (index == 0 && nums[index] < nums[n - 1]) {
                        return true;
                }
                return false;
        }

    public:
        int findMin(vector<int> &nums)
        {
                int n = nums.size();
                int left = 0, right = n - 1;
                int mid;
                while (left <= right) {
                        mid = left + (right - left) / 2;
                        if (isLowest(nums, mid)) {
                                return nums[mid];
                        }
                        if (nums[mid] > nums[right]) {
                                left = mid + 1;

                        } else if (nums[mid] < nums[left]) {
                                right = mid - 1;
                        } else { // nums[left]<= nums[mid] <= nums[right]
                                return nums[left];
                        }
                }
                return nums[0];
        }
};

leetcode hot 100 rewrite

#include <vector>
using std::vector;

class Solution {
    public:
        int findMin(vector<int> &nums)
        {
                // n == nums.length
                // 1 <= n <= 5000
                // -5000 <= nums[i] <= 5000
                // All integers in nums are distinct.
                // nums was originally an array sorted in ascending order, and was rotated between 1 and n times.

                int n = nums.size();
                int left = 0, right = n - 1, mid = 0;

                if (nums[0] <= nums[n - 1]) // Rotated n times.
                        return nums[0];

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

                        if (mid > 0 && nums[mid - 1] > nums[mid])
                                return nums[mid];

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

                return nums[mid];
        }
};