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

发表于 | 分类于 |
字数统计: 383 | 阅读时长 ≈ 1

链接：https://leetcode-cn.com/problems/find-minimum-in-rotated-sorted-array/

题面

给定一个旋转后的有序数组，找出数组中的最小值

通过考虑数组中的最后一个元素 x：在最小值右侧的元素（不包括最后一个元素本身），它们的值一定都严格小于 x；而在最小值左侧的元素，它们的值一定都严格大于 x。因此，我们可以根据这一条性质，通过二分查找的方法找出最小值。

如果nums[mid] < nums[r]: 则说明nums[mid]是最小值右侧的元素，只需要在左半部分区间进行搜索
否则的话，说明nums[mid]是最小值左侧的元素，因此在右半部区间进行搜索。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int findMin(vector<int>& nums) {
        int l = 0, r = (int)nums.size() - 1;
        while (l < r) {
            int mid = l + (r - l) / 2;
            if (nums[mid] < nums[r]) {
                r = mid;
            }
            else {
                l = mid + 1;
            }
        }
        return nums[l];
    }
};

链接：https://leetcode-cn.com/problems/find-minimum-in-rotated-sorted-array-ii/
如果新增一个条件是数组中存在重复元素，做法也是类似的
当nums[mid] == nums[r]的时候，将右端点左移一位进行下一次的查找即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    int findMin(vector<int>& nums) {
        int l = 0, r = nums.size() - 1;
        while(l < r) {
            int mid = l + (r - l) / 2;
            if (nums[mid] == nums[r]) {
                r--;
            }
            else if (nums[mid] < nums[r]) {
                r = mid;
            } 
            else if (nums[mid] > nums[r]) {
                l = mid + 1;
            }
        }
        return nums[l];
    }
};