Cover image for Interview Classic 150 Questions P153 Find Minimum in Rotated Sorted Array

Interview Classic 150 Questions P153 Find Minimum in Rotated Sorted Array

(Updated: )
algorithm
, , ,
Timeline

Timeline

2025-12-04

init

Divide and Conquer

Title:

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 finding peak element.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#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 unique.
                // nums was originally sorted in ascending order and 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];
        }
};