旋转数组二分

Posted on Edited on Symbols count in article: 4.4k Reading time ≈ 4 mins.

1 寻找峰值

找到任意一个峰值，你可以假设 nums[-1] = nums[n] = -∞ 。

1.1 二分法（不怎么优雅）

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

1.2 二分法（优雅）

其实只要搞清楚我们「二分」什么内容，根本不会存在说用哪种方式才能写过的情况。 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    int findPeakElement(vector<int>& nums) {
        int l = 0, r = nums.size()-1;
        while(l < r){
            int m = (l + r) >> 1;
            // 这里m+1不会越界，因为l <= m < r，所以m-1是可能越界的，m+1必然不会越界
            if(nums[m] > nums[m+1])
                r = m;  // 注意
            else
                l = m + 1;  // 注意
        }
        return l;
    }
};

2 搜索旋转排序数组（无重复）

2.1 二分法（有点丑，但好理解）

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
class Solution {
public:
    int search(vector<int>& nums, int target) {
        int n = nums.size(), l = 0, r = n - 1;
        while(l <= r){
            int m = (l + r) >> 1;
            if(nums[m] == target) return m;
            
            // 因为如果就俩数，除以二肯定l == m, r == m+1
            if(nums[l] == nums[m]){
                if(r < n && nums[r] == target) return r;
                else return -1;
            }
            else if(nums[l] < nums[m]){ // 左边正常
                if(target >= nums[l] && target < nums[m]) 
                    r = m - 1;
                else 
                    l = m + 1;
            }
            else{ // 右边正常
                if(target > nums[m] && target <= nums[r])
                    l = m + 1;
                else
                    r = m - 1;
            }
        }
        return -1;
    }
};

2.2 二分法（优雅）（与l比较）

  • 牢记：左区间是[l, m]，右区间是(m+1, r]，所以“左区间正常”包含等号
  • 由于前一步 if(nums[m] == target) return m; 已经判定了nums[m] != target，所以后面对target和nums[m]的比较不带等号 
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    class Solution {
    public:
        int search(vector<int>& nums, int target) {
            int n = nums.size(), l = 0, r = n - 1;
            while(l <= r){
                int m = (l + r) >> 1;
                if(nums[m] == target) return m;
                if(nums[l] <= nums[m]){ // 左边正常
                    if(target >= nums[l] && target < nums[m]) 
                        r = m - 1;
                    else 
                        l = m + 1;
                }
                else{ // 右边正常
                    if(target > nums[m] && target <= nums[r])
                        l = m + 1;
                    else
                        r = m - 1;
                }
            }
            return -1;
        }
    };

2022.08.10（与r比较）

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
// while等号和不等号
class Solution {
public:
    int search(const vectorr<int>& arr, int target) {
        int l = 0, r = arr.size() - 1;
        while(l < r){
            int m = (l+r)/2;
            if(arr[m] == target) return m;
            if(arr[m] < arr[r]){ // 右边正常（互不相同所以没等于）
                if(target > arr[m] && target<=arr[r]) l = m + 1;
                else r = m - 1;
            }else{ // 左边正常
                if(target >= arr[l] && target<arr[m]) r = m - 1;
                else l = m + 1;
            }
        }
        return arr[l] == target ? l : -1;
    }
};

class Solution {
public:
    int search(vector<int>& arr, int target) {
        int l = 0, r = arr.size() - 1;
        while(l <= r){
            int m = (l+r)/2;
            if(arr[m] == target) return m;
            if(arr[m] < arr[r]){ // 右边正常（互不相同所以没等于）
                if(target > arr[m] && target<=arr[r]) l = m + 1;
                else r = m - 1;
            }else{ // 左边正常
                if(target >= arr[l] && target<arr[m]) r = m - 1;
                else l = m + 1;
            }
        }
        return -1;
    }
};

3 寻找旋转排序数组中的最小值（无重复）

图解

3.1 二分法

  • 如上图所示，如果每次以nums[l] < nums[m]为条件虽然可以认定左区间是单调的，但是就全局最小值而言无法区分图1和图2的；但是以nums[m] < nums[r]可以认定右区间单调，且可以区分所有最小值情况。一定要理解二分时收缩区间的含义。
  • 不能动不动l = m + 1，r = m - 1这种大起大和的方式，因为目的是求极值而不是target，target不等于的时候，某一边确实可以跳；但是求极值时，例如下面代码中r = m，因为不确定nums[m]是不是极值，所以不能写成r = m - 1 
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    class Solution {
    public:
        int findMin(vector<int>& nums) {
            int l = 0, r = nums.size()-1;
            while(l < r){
                int m = (l + r) / 2;
                if(nums[m] < nums[r])
                    r = m; // 注意
                else
                    l = m + 1;  // 注意
            }
            return nums[l];
        }
    };

为什么左右不对称？为什么比较mid与right而不比较mid与left？能不能通过比较mid与left来解决问题？
左右不对称的原因是：这是循环前升序排列的数，左边的数小，右边的数大，而且我们要找的是最小值，肯定是偏向左找，所以左右不对称了。
为什么比较mid与right而不比较mid与left？具体原因前面已经分析过了，简单讲就是因为我们找最小值，要偏向左找，目标值右边的情况会比较简单，容易区分，所以比较mid与right而不比较mid与left。
那么能不能通过比较mid与left来解决问题？能，转换思路，不直接找最小值，而是先找最大值，最大值偏右，可以通过比较mid与left来找到最大值，最大值向右移动一位就是最小值了（需要考虑最大值在最右边的情况，右移一位后对数组长度取余）。

4 寻找旋转排序数组中的最小值 II（有重复）

4.1 二分

由于相等时无法确认二分的方向，所以选择慎重地小幅度收缩1步 

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

4.2 栈+二分

由于相等时无法确认二分的方向，所以用栈保存下来可能的区间，留作继续二分 

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
class Solution {
public:
    int findMin(vector<int>& arr) {
        stack<int> stk;
        stk.push(0);
        stk.push(arr.size()-1);
        int l=0, r=0;
        int res = 0x3f3f3f3f;
        while(!stk.empty()){
            r = stk.top(); stk.pop();
            l = stk.top(); stk.pop();
            while(l < r){
                int m = (l + r) / 2;
                if(arr[m] == arr[r]){
                    stk.push(l);
                    stk.push(m-1);
                    l = m + 1;
                }else if(arr[m] < arr[r]){
                    r = m;
                }else if(arr[m] > arr[r]){
                    l = m + 1;
                }
            }
            if(l <= r) // !
                res = min(res, arr[r]);
        }
        return res;
    }
};