二分 & 三分查值问题-一一网

这是我参与更文挑战的第 15 天，活动详情查看：更文挑战

题目描述

这是 LeetCode 上的 852. 山脉数组的峰顶索引 ，难度为简单。

Tag : 「二分」、「三分」

符合下列属性的数组 arr 称为山脉数组：

arr.length >= 3
存在 i（0 < i < arr.length - 1） 使得：
- arr[0] < arr[1] < ... arr[i-1] < arr[i]
- arr[i] > arr[i+1] > ... > arr[arr.length - 1]

给你由整数组成的山脉数组 arr ，返回任何满足 arr[0] < arr[1] < ... arr[i - 1] < arr[i] > arr[i + 1] > ... > arr[arr.length - 1] 的下标 i 。

示例 1：

输入：arr = [0,1,0]
输出：1
复制代码

示例 2：

输入：arr = [0,2,1,0]
输出：1
复制代码

示例 3：

输入：arr = [0,10,5,2]
输出：1
复制代码

示例 4：

输入：arr = [3,4,5,1]
输出：2
复制代码

示例 5：

输入：arr = [24,69,100,99,79,78,67,36,26,19]
输出：2
复制代码

提示：

3 <= arr.length <= $10^4$
0 <= arr[i] <= $10^6$
题目数据保证 arr 是一个山脉数组

进阶：很容易想到时间复杂度 O(n) 的解决方案，你可以设计一个 O(log(n)) 的解决方案吗？

二分

往常我们使用「二分」进行查值，需要确保序列本身满足「二段性」：当选定一个端点（基准值）后，结合「一段满足 & 另一段不满足」的特性来实现“折半”的查找效果。

但本题求的是峰顶索引值，如果我们选定数组头部或者尾部元素，其实无法根据大小关系“直接”将数组分成两段。

但可以利用题目发现如下性质：由于 arr 数值各不相同，因此峰顶元素左侧必然满足严格单调递增，峰顶元素右侧必然不满足。

因此 以峰顶元素为分割点的 arr 数组，根据与前一元素/后一元素的大小关系，具有二段性：

峰顶元素左侧满足 $arr[i-1] < arr[i]$ 性质，右侧不满足
峰顶元素右侧满足 $arr[i] > arr[i+1]$ 性质，左侧不满足

因此我们可以选择任意条件，写出若干「二分」版本。

代码：

class Solution {
    // 根据 arr[i-1] < arr[i] 在 [1,n-1] 范围内找值
    // 峰顶元素为符合条件的最靠近中心的元素
    public int peakIndexInMountainArray(int[] arr) {
        int n = arr.length;
        int l = 1, r = n - 1;
        while (l < r) {
            int mid = l + r + 1 >> 1;
            if (arr[mid - 1] < arr[mid]) {
                l = mid;
            } else {
                r = mid - 1;
            }
        }
        return r;
    }
}
复制代码

class Solution {
    // 根据 arr[i] > arr[i+1] 在 [0,n-2] 范围内找值
    // 峰顶元素为符合条件的最靠近中心的元素值
    public int peakIndexInMountainArray(int[] arr) {
        int n = arr.length;
        int l = 0, r = n - 2;
        while (l < r) {
            int mid = l + r >> 1;
            if (arr[mid] > arr[mid + 1]) {
                r = mid;
            } else {
                l = mid + 1;
            }
        }
        return r;
    }
}
复制代码

class Solution {
    // 根据 arr[i-1] > arr[i] 在 [1,n-1] 范围内找值
    // 峰顶元素为符合条件的最靠近中心的元素的前一个值
    public int peakIndexInMountainArray(int[] arr) {
        int n = arr.length;
        int l = 1, r = n - 1;
        while (l < r) {
            int mid = l + r >> 1;
            if (arr[mid - 1] > arr[mid]) {
                r = mid;
            } else {
                l = mid + 1;
            }
        }
        return r - 1;
    }
}
复制代码

class Solution {
    // 根据 arr[i] < arr[i+1] 在 [0,n-2] 范围内找值
    // 峰顶元素为符合条件的最靠近中心的元素的下一个值
    public int peakIndexInMountainArray(int[] arr) {
        int n = arr.length;
        int l = 0, r = n - 2;
        while (l < r) {
            int mid = l + r + 1 >> 1;
            if (arr[mid] < arr[mid + 1]) {
                l = mid;
            } else {
                r = mid - 1;
            }
        }
        return r + 1;
    }
}
复制代码

时间复杂度： $O(\log{n})$
空间复杂度： $O(1)$

三分

事实上，我们还可以利用「三分」来解决这个问题。

顾名思义，「三分」就是使用两个端点将区间分成三份，然后通过每次否决三分之一的区间来逼近目标值。

具体的，由于峰顶元素为全局最大值，因此我们可以每次将当前区间分为 $[l, m1]$ 、 $[m1, m2]$ 和 $[m2, r]$ 三段，如果满足 $arr[m1] > arr[m2]$ ，说明峰顶元素不可能存在与 $[m2, r]$ 中，让 $r = m2 – 1$ 即可。另外一个区间分析同理。

代码：

class Solution {
    public int peakIndexInMountainArray(int[] arr) {
        int n = arr.length;
        int l = 0, r = n - 1;
        while (l < r) {
            int m1 = l + (r - l) / 3;
            int m2 = r - (r - l) / 3;
            if (arr[m1] > arr[m2]) {
                r = m2 - 1;
            } else {
                l = m1 + 1;
            }
        }
        return r;
    }
}
复制代码