【常见题型总结】二分以及为何能二分（二段性的拓展）

题目描述

这是 LeetCode 上的 「162. 寻找峰值」 ，难度为 「中等」。

Tag : 「二分」

峰值元素是指其值严格大于左右相邻值的元素。

给你一个整数数组 nums，找到峰值元素并返回其索引。数组可能包含多个峰值，在这种情况下，返回 任何一个峰值 所在位置即可。

你可以假设 nums[-1] = nums[n] = -∞ 。

你必须实现时间复杂度为 的算法来解决此问题。

示例 1：

输入：nums = [1,2,3,1]

输出：2

解释：3 是峰值元素，你的函数应该返回其索引 2。

示例 2：

输入：nums = [1,2,1,3,5,6,4]

输出：1 或 5 

解释：你的函数可以返回索引 1，其峰值元素为 2；
     或者返回索引 5， 其峰值元素为 6。

提示：

• 对于所有有效的 i 都有 nums[i] != nums[i + 1]

模拟

由于数据范围只有 ，使用线性扫描找峰值的模拟做法也是没有问题。

代码：

class Solution {
    public int findPeakElement(int[] nums) {
        int n = nums.length;
        for (int i = 0; i < n; i++) {
            boolean ok = true;
            if (i - 1 >= 0) {
                if (nums[i - 1] >= nums[i]) ok = false;
            }
            if (i + 1 < n) {
                if (nums[i + 1] >= nums[i]) ok = false;
            }
            if (ok) return i;
        }
        return -1;
    }
}

• 时间复杂度：
• 空间复杂度：

二分

题目让我们实现一个 算法，这是对使用「二分」的强烈暗示。

和往常的题目一样，「我们应当从是否具有「二段性」来考虑是否可以进行「二分」」。

不难发现，「如果」 在确保有解的情况下，我们可以根据当前的分割点 与左右元素的大小关系来指导 或者 的移动。

假设当前分割点 满足关系 的话，一个很简单的想法是 可能为峰值，而 必然不为峰值，于是让 ，从左半部分继续找峰值。

估计不少同学靠这个思路 AC 了，只能说做法对了，分析没对。

上述做法正确的前提有两个：

1. 对于任意数组而言，一定存在峰值（一定有解）；
2. 二分不会错过峰值。

我们分别证明一下。

「证明 ：对于任意数组而言，一定存在峰值（一定有解）」

根据题意，我们有「数据长度至少为 」、「越过数组两边看做负无穷」和「相邻元素不相等」的起始条件。

我们可以根据数组长度是否为 进行分情况讨论：

1. 数组长度为 ，由于边界看做负无穷，此时峰值为该唯一元素的下标；

2. 数组长度大于 ，从最左边的元素 开始出发考虑：

   • 如果 ，那么最左边元素 就是峰值（结合左边界为负无穷）；
   • 如果 ，由于已经存在明确的 和 大小关系，我们将 看做边界， 看做新的最左侧元素，继续往右进行分析：

     • 如果在到达数组最右侧前，出现 ，说明存在峰值位置 （当我们考虑到 ，必然满足 大于前一元素的前提条件，当然前一元素可能是原始左边界）；
     • 到达数组最右侧，还没出现 ，说明数组严格递增。此时结合右边界可以看做负无穷，可判定 为峰值。

「综上，我们证明了无论何种情况，数组必然存在峰值。」

「证明 ：二分不会错过峰值」

其实基于「证明 」，我们很容易就可以推理出「证明 」的正确性。

整理一下由「证明 」得出的推理：「如果当前位置大于其左边界或者右边界，那么在当前位置的右边或左边必然存在峰值。」

「换句话说，对于一个满足 的位置， 的右边一定存在峰值；或对于一个满足 的位置， 的左边一定存在峰值。」

因此这里的「二段性」其实是指：「在以 为分割点的数组上，根据 与 的大小关系，可以确定其中一段满足「必然有解」，另外一段不满足「必然有解」（可能有解，可能无解）。」

❝

如果不理解为什么「证明 」的正确性可以由「证明 」推导而出的话，可以重点看看「证明 」的第 点的证明。

❞

「至此，我们证明了始终选择大于边界一端进行二分，可以确保选择的区间一定存在峰值，并随着二分过程不断逼近峰值位置。」

另外，为了照顾还在纠结使用什么“模板”的同学，特意写了两个版本。但其实只要搞清楚我们「二分」什么内容，根本不会存在说用哪种方式才能写过的情况。

代码：

class Solution {
    public int findPeakElement(int[] nums) {
        int n = nums.length;
        int l = 0, r = n - 1;
        while (l < r) {
            int mid = l + r >> 1;
            if (nums[mid] > nums[mid + 1]) r = mid;
            else l = mid + 1;
        }
        return r;
    }
}

class Solution {
    public int findPeakElement(int[] nums) {
        int n = nums.length;
        if (n == 1) return 0;
        int l = 0, r = n - 1;
        while (l < r) {
            int mid = l + r + 1 >> 1;
            if (nums[mid] > nums[mid - 1]) l = mid;
            else r = mid - 1;
        }
        return r;
    }
}

• 时间复杂度：
• 空间复杂度：

总结

「通过本题，我们可以对「二分」有进一步的认识。」

「最早在 33. 搜索旋转排序数组 中，我们强调，二分的本质是「二段性」而非「单调性」，而经过本题，我们进一步发现「二段性」还能继续细分，不仅仅只有满足 特性（满足/不满足）的「二段性」可以使用二分，满足 特性（一定满足/不一定满足）也可以二分。」

最后

这是我们「刷穿 LeetCode」系列文章的第 No.162 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先把所有不带锁的题目刷完。

在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。

为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：https://github.com/SharingSource/LogicStack-LeetCode

在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。

更多更全更热门的「笔试/面试」相关资料可访问排版精美的 合集新基地 🎉🎉