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

题意

给定旋转一次的升序无重复数组，找到最小元素。要求 $O(\log n)$ 。

思路

比较 nums[mid] 与 nums[r]：若 nums[mid] < nums[r]，右半区间 [mid, r] 有序，最小值一定在 [l, mid]（含 mid）；否则右半区间无序（旋转点在右半），最小值在 [mid+1, r]。

循环条件 l < r（而非 l <= r），因为当 l == r 时区间只有一个元素，即为答案。

代码

cpp

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#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    int findMin(vector<int> &nums) {
        int l = 0, r = nums.size() - 1;
        while (l < r) {
            int mid = (l + r) / 2;
            if (nums[mid] < nums[r])
                r = mid;
            else
                l = mid + 1;
        }
        return nums[l];
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    vector<int> a(n);
    for (int &x : a)
        cin >> x;
    cout << Solution().findMin(a) << '\n';
    return 0;
}

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24#!/usr/bin/env python3
from typing import List


class Solution:
    def findMin(self, nums: List[int]) -> int:
        l, r = 0, len(nums) - 1
        while l < r:
            m = (l + r) // 2
            if nums[m] < nums[r]:
                r = m
            else:
                l = m + 1
        return nums[l]


def main():
    n = int(input())
    a = list(map(int, input().split()))
    print(Solution().findMin(a))


if __name__ == "__main__":
    main()

复杂度

时间复杂度： $O(\log n)$ 。
空间复杂度： $O(1)$ 。

总结

旋转数组找最小值与找 target 的二分模式不同：不判断"哪半有序"，而是比较中点与右端点来决定最小值落在哪半。nums[mid] < nums[r] 说明 [mid, r] 有序，最小值不可能在 mid 右侧（不含 mid），所以 r = mid。

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

目录

题意

思路

代码

复杂度

总结