leetcode153：寻找旋转排序数组中的最小值

题目链接

leetcode

题目描述

已知一个长度为 n 的数组，预先按照升序排列，经由 1 到 n 次 旋转 后，得到输入数组。例如，原数组 nums = [0,1,2,4,5,6,7] 在变化后可能得到：

• 若旋转 4 次，则可以得到 [4,5,6,7,0,1,2]
• 若旋转 7 次，则可以得到 [0,1,2,4,5,6,7]

注意，数组 [a[0], a[1], a[2], ..., a[n-1]] 旋转一次 的结果为数组 [a[n-1], a[0], a[1], a[2], ..., a[n-2]] 。
给你一个元素值 互不相同 的数组 nums ，它原来是一个升序排列的数组，并按上述情形进行了多次旋转。请你找出并返回数组中的 最小元素 。
设计一个时间复杂度为 O(log n) 的算法解决此问题。

C++ 代码

#include <iostream>
#include <vector>
using namespace std;

/*
    二分查找

    假设数组中最后一个元素是 x：
        在最小值右侧的元素（不包括最后一个元素本身），它们的值都小于 x；
        在最小值左侧的元素，它们的值都大于等于 x。
    根据这一条性质，二分找出最小值。

    时间复杂度：O(logn)
        其中 n 是数组 nums 的长度。
        在二分查找的过程中，每一步忽略一半的区间，时间复杂度为 O(logn)。
    空间复杂度：O(1)
*/
class Solution {
public:
    int findMin(vector<int>& nums) {
        // 空数组
        if (nums.empty()) {
            return -1;
        }
        // 特殊情况：数组完全单调
        if (nums.back() >= nums[0]) {
            return nums[0];
        }

        int left = 0, right = nums.size()-1;
        // 搜索区间 [left, right] 左闭右闭
        while (left < right) {
            int mid = left + (right - left) / 2;

            if (nums[mid] < nums[right]) {
                // 最小值在左边（包含 mid）
                right = mid;
            } else {
                // 最小值在右边（不包含 mid）
                left = mid + 1;
            }
        }

        // 此时 left == right，指向最小值
        return nums[right];
    }
};

// 辅助函数：打印数组
void printArray(const vector<int>& nums) {
    cout << "[";
    for (size_t i = 0; i < nums.size(); i++) {
        cout << nums[i];
        if (i != nums.size() - 1) cout << ",";
    }
    cout << "]";
}

int main() {
    Solution solution;
    vector<vector<int>> nums_cases = {
        {3,4,5,1,2},
        {4,5,6,7,0,1,2},
        {11,13,15,17}
    };

     for (size_t i = 0; i < nums_cases.size(); i++) {
        auto& nums = nums_cases[i];

        cout << "Input: nums = ";
        printArray(nums);
        cout << endl;
        int result = solution.findMin(nums);
        cout << "Output: " << result << endl;
    }

    return 0;
}