模块三：二分——153.寻找旋转排序数组中的最小值

题目描述

题目链接：153.寻找旋转排序数组中的最小值

根据题目的要求时间复杂度为O(log N)可知需要使用二分查找。

算法原理

解法一：暴力查找

遍历数组一遍，寻找数组最小值并返回，时间复杂度为O(N)，因为需要遍历数组一遍，与本题要求不符，但是可以AC
PS：写这个解法的原因是因为我们最好想也最好写的解法就是暴力解法，经验不足的话都是靠暴力解法来做题的，搞懂了暴力解法之后，我们再去根据所学的算法和经验，借助画图，根据题目要求来优化我们的暴力解法，会让我们的基础比较扎实。

解法二：二分查找

⼆分的本质：找到⼀个判断标准，使得查找区间能够⼀分为⼆。（二段性）
我们可以把数组划分成两部分，其中C点就是我们要的答案。通过图像我们可以发现， [A，B] 区间内的点都是严格⼤于 D 点的值的， C 点的值是严格⼩于 D 点的值的。但是当 [C，D] 区间只有⼀个元素的时候， C 点的值是可能等于 D 点的值的。
因此，初始化左右两个指针 left ， right ：然后根据 mid 的落点，我们可以这样划分下⼀次查询的区间：

• 当 mid 在 [A，B] 区间的时候，也就是 mid 位置的值严格⼤于 D 点的值，下⼀次查询区间在 [mid + 1，right]上；
• 当 mid 在 [C，D] 区间的时候，也就是 mid 位置的值严格⼩于等于 D 点的值，下次查询区间在 [left，mid] 上。
• 当区间⻓度变成 1 的时候，就是我们要找的结果。

疑问

请问可以选择A点作为参照物吗？大家可以想一想
答案放在解法二的C++代码部分解答。

代码实现

解法一：暴力查找

class Solution {
public:
    int findMin(vector<int>& nums) {
        int ret = INT_MAX;
        for(int i = 0;i < nums.size();++i){
            ret = min(ret,nums[i]);
        }
        return ret;
    }
};
1
2
3
4
5
6
7
8
9
10

解法二：C++

class Solution {
public:
    int findMin(vector<int>& nums) {
        //根据二段性可以使用二分
        int left = 0,right = nums.size() - 1;

        if(nums[left] < nums[right])return nums[left];
        
        while(left < right){
            int mid = left + (right - left) / 2;
            //答案是可以的，但是需要写成if(nums[mid] >= nums[0])，因为
            //当left = mid的时候，即只有两个数的时候，我们会跑去AB部分找答案
            //这会导致部分用例无法通过
            if(nums[mid] > nums[nums.size() - 1])left = mid + 1;
            else right = mid;
        }
        return nums[left];
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

Java

class Solution {
    public int findMin(int[] nums) {
        int left = 0, right = nums.length - 1;
        int x = nums[right]; // 标记⼀下最后⼀个位置的值
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] > x)
                left = mid + 1;
            else
                right = mid;
        }
        return nums[left];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14