「二分法」-山峰数组-加深对模版的理解

发表于 更新于 Artalk： loading...
二分

前言

本文承继acwing算法基础课笔记2-二分法

全部为左闭右闭写法

题目

image-20220330162109224

思路

初始想法

同旋转数组的思路一样，每次搜索将区间分成一个有序的部分和一个无序的部分。

本题设定存在“山峰值”，那么每次划分一定是严格的 一部分有序，另一部分无序。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public int peakIndexInMountainArray(int[] arr) {
        int n = arr.length;
        int l = 1, r = n - 2;
        while (l <= r) {
            int mid = l + r  >> 1; ///
            if (arr[mid] >= arr[l]) {
                if (arr[mid - 1] > arr[mid]) r = mid - 1;
                else l = mid + 1;
            } else {
                r = mid - 1;
            }
        }
        return r;
    }
}

细节：

  1. 根据题目定义，山峰不可能出现在数组头或者尾部，因此初值 l=1，r=n-2

  2. 当arr[mid]值小于arr[l]时，此时arr[mid]一定处于下降侧/右侧，

  3. 当arr[mid]值大于arr[l]时，分情况讨论：

    1. 若arr[mid-1] > arr[mid],一定处于下降侧，则区间向左侧收紧，且mid一定不是山峰，r = mid - 1
    2. 反之 l = mid + 1

但是，这样判断很不优雅，而且我在写代码的过程中也发现了更优的判断方法：

  • arr[mid - 1] < arr[mid] 一定处于上升侧
  • arr[mid - 1] > arr[mid] 一定处于下降侧

基于此，更新后的代码

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
    public int peakIndexInMountainArray(int[] arr) {
        int n = arr.length;
        int l = 1, r = n - 2;
        while (l < r) {
            int mid = l + r + 1>> 1; 
            if (arr[mid - 1] <= arr[mid]) l = mid;
            else r = mid - 1;
        }
        return l;
    }
}

细节：

这里的arr[mid - 1] <= arr[mid]，意义

  1. arr[mid]在峰值的左侧，等价于 check(mid) <= target，向右收紧搜索区间
  2. 此时的arr[mid]是可能为峰值的，搜索区间的端点要取到mid

综上两点，搜索区间更新方式为 l = mid; 。别忘了 mid=l+r+12mid=\frac{l+r+\bold{1}}{2}

关于更新方式，请记住（仅限本人常用的模板一二）

R+1=LR + 1 = L

l=mid -->r就更新为r=mid-1

l=mid+1 -->r就更新为r=mid

左端点更新为r = mid - 1

亿点点拓展-找不同

下面给出几组正确代码

逻辑是一致的，重点在于不同的写法

退出循环条件为 l < r

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
    public int peakIndexInMountainArray(int[] arr) {
        int n = arr.length;
        int l = 1, r = n - 2;
        while (l < r) {
            int mid = l + r >> 1; 
            if (arr[mid] <= arr[mid + 1]) l = mid + 1;
            else r = mid;
        }
        return l;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
    public int peakIndexInMountainArray(int[] arr) {
        int n = arr.length;
        int l = 1, r = n - 2;
        while (l < r) {
            int mid = l + r + 1>> 1; 
            if (arr[mid - 1] >= arr[mid]) r = mid - 1;
            else l = mid;
        }
        return l;
    }
}

退出循环条件为 l <= r

2.1

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
    public int peakIndexInMountainArray(int[] arr) {
        int n = arr.length;
        int l = 1, r = n - 2;
        while (l <= r) {
            int mid = l + r >> 1; 
            if (arr[mid - 1] >= arr[mid]) r = mid - 1;
            else l = mid + 1;
        }
        return l - 1;
    }
}

2.2

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
    public int peakIndexInMountainArray(int[] arr) {
        int n = arr.length;
        int l = 1, r = n - 2;
        while (l <= r) {
            int mid = l + r >> 1; 
            if (arr[mid + 1] >= arr[mid]) l = mid + 1;
            else r = mid - 1;
        }
        return l;
    }
}

2.1最后返回值是l-1也就是r，2.2是l

思考一下为什么？(不思考也没事，这种麻烦也是不选用l<=r写法的原因)

个人理解

bullshit, 就别用这种退出循环的方式！！！