Day75 | 灵神 | 二分查找 寻找旋转排序数组中的最小值 搜索旋转排序数组

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

153. 寻找旋转排序数组中的最小值 - 力扣（LeetCode）

思路：

思路就是如何判断nums[mid]是在最小值的左侧还是右侧

这道题第一次做还是没啥思路，看到灵神说和最后一个数a进行比较就懂了

不管旋转没有旋转，只要nums[mid]<=a，那说明最小值肯定在[l,mid]之中

只要nums[mid]>a，那说明最小值肯定在[mid,r)之中

具体看灵神怎么说：

我们需要判断 x 和数组最小值的位置关系，谁在左边，谁在右边？

把 x 与最后一个数 nums[n−1] 比大小：

如果 x>nums[n−1]，那么可以推出以下结论：
1.nums 一定被分成左右两个递增段；
2.第一段的所有元素均大于第二段的所有元素；
3.x 在第一段。
4.最小值在第二段。
所以 x 一定在最小值的左边。
如果 x≤nums[n−1]，那么 x 一定在第二段。（或者 nums 就是递增数组，此时只有一段。）
x 要么是最小值，要么在最小值右边。
所以，只需要比较 x 和 nums[n−1] 的大小关系，就间接地知道了 x 和数组最小值的位置关系，从而不断地缩小数组最小值所在位置的范围，二分找到数组最小值。

完整代码：

笔者写的左闭右开区间

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=nums.size();
        int num=nums[r-1];
        while(l<r)
        {
            int mid=l+(r-l)/2;
            if(nums[mid]<=num)
                r=mid;
            else
                l=mid+1;
        }
        return nums[l];
    }
};

33.搜索旋转排序数组

33. 搜索旋转排序数组 - 力扣（LeetCode）

思路：

如果笔者直接做这个题那可能就蒙圈了，但是笔者是做了153才来做的

所以一下就想到找最小值然后分成两段再进行两次二分这个思路

直接开干得到如下代码

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
40
41
42
43
44
45
46
47
48
class Solution {
public:
    //找最小值
    int findMin(vector<int>& nums)
    {
        int l=0,r=nums.size();
        int num=nums[r-1];
        while(l<r)
        {
            int mid=l+(r-l)/2;
            if(nums[mid]<=num)
                r=mid;
            else
                l=mid+1;
        }
        return r;
    }
    //二分查找
    int b_search(vector<int>& nums, int l,int r,int target)
    {
        while(l<r) 
        {
            int mid=l+(r-l)/2;
            if(target<=nums[mid])
                r=mid;
            else
                l=mid+1;
        }
        return (l<nums.size()&&nums[l]==target)?l:-1;
    }
    int search(vector<int>& nums, int target) {
        //找最小值的下标
        int l=findMin(nums);
        //说明数组被分成了两段递增
        if(l!=0)
        {
            //搜索后面一段
            int a=b_search(nums,l,nums.size(),target);
            //搜索前面一段
            int b=b_search(nums,0,l,target);
            //哪段里面找到了返回哪段
            return a!=-1?a:b;
        }
        //说明数组没有被分开，搜索整个数组
        else
            return b_search(nums,0,nums.size(),target);
    }
};

需要注意我在二分查找target中写的l和nums.size()的关系判断，因为我用的是左闭右开区间，所以如果最后没找到target的话，并且数组大小为1，那最后l==r==nums.size()了，就会越界

而灵神的判断比我更加精巧，只用了两次二分，一次查找最小，一次找target

1
2
3
if(target>nums.back())
          return b_search(nums,0,index,target);
      return b_search(nums,index,nums.size(),target);

target>nums.back()，如果数组只有一段，那说明数组中没有target，传入的其实是l=0,r=0

如果数组有两段，第一段的所有数字都大于第二段，那target肯定就是在第一段或者不存在，那就是[0，index)

target<=nums.back()，如果数组只有一段，那肯定数组中有target，传入的其实实际上是l=0,r=nums.size()，即搜索整个数组，如果数组有两段，第一段的所有数字都大于第二段，所以target肯定在第二段，传入的就是l=index,r=nums.size()

完整代码：

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
class Solution {
public:
    int b_search(vector<int>& nums, int l,int r,int target)
    {
        while(l<r) 
        {
            int mid=l+(r-l)/2;
            if(target<=nums[mid])
                r=mid;
            else
                l=mid+1;
        }
        return nums[l]==target?l:-1;
    }
    int findMin(vector<int>& nums)
    {
        int l=0,r=nums.size();
        int num=nums[r-1];
        while(l<r)
        {
            int mid=l+(r-l)/2;
            if(nums[mid]<=num)
                r=mid;
            else
                l=mid+1;
        }
        return r;
    }
    int search(vector<int>& nums, int target) {
        int index=findMin(nums);
        if(target>nums.back())
            return b_search(nums,0,index,target);
        return b_search(nums,index,nums.size(),target);
    }
};