leetcode-33. 搜索旋转排序数组

本文最后更新于：2022年8月2日 晚上

二分：整数二分细节比较多，实数二分比较简单

二段性：找一个性质，第一段满足，第二段不满足，二分出边界点，边界点就是，满足性质的第一段的最后一个数。

两次2分，第一次二分出来数组中的断层的点，第二次在单调序列中二分找tar

注意：

  • 这道题要注意：如果面试官问你再旋转一次怎么做，做法还是一样的，无论旋转几次，最多只有2段递增序列
  • 33的加强版是81题； 这两个题的基础是153和154题。
  • 33-查找旋转数组不重复；81-查找旋转数组可重复复；153-旋转数组最小值不重复；154旋转数字最小值重复，这几个一起做做，二分的题目太难太细节，需要对比
  • 二分。重点在于先判断哪半段是有序的，然后判断目标是否在有序的那半里面。
  • 基础: 153.33. 进阶：154.81.

思路：

两次二分，第一次二分找到左边区间的最大值；判断target在哪个区间，重新划分区间；第二次二分在新的区间中找target

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
class Solution {
public:
    int search(vector<int>& nums, int target) {
        // 想法1：找到数组中下标i，满足nums[i] > nums[i+1], 然后恢复数组为升序
        // 接着使用二分，找tar
        // y总思路：一般是有序，找一个二段性就可以二分，本题数组中间断开，所以先找断开的点在哪里
        // 然后判断target是在断点的左边区间还是右边区间，再该区间中再次使用二分找到target
        
        int l = 0, r = nums.size() - 1;
        while (l < r)
        {
            int mid = l + r + 1 >> 1;
            if (nums[mid] >= nums[0]) l = mid;
            else r = mid - 1;
        }
        // 此时 ，nums[r] 就是 前半部分的最大值

        // 接着判断target在哪个部分
        if (target >= nums[0]) l = 0;
        else l = r + 1, r = nums.size() -1;

        // 继续二分，在目标有序区间中找到target
        while (l < r)
        {
            int mid = l + r >> 1;
            if (nums[mid] >= target) r = mid;
            else l = mid + 1;
        }
        // 此时的l=r就是target的下标，如果没找到，就是-1
        if (nums[r] == target) return r;
        else return -1;
    }
};