【宫水三叶の剑指精选】详解何为二段性丢失，以及如何恢复二段性进行二分

朴素解法

一个朴素的解法是直接对数组进行线性扫描，并在遍历过程中维护一个全局最小值。

代码：

import java.util.ArrayList;
public class Solution {
    public int minNumberInRotateArray(int [] array) {
        int ans = 0x3f3f3f3f;
        for (int i : array) ans = Math.min(ans, i);
        return ans;
    }
}

时间复杂度： $O(n)$
空间复杂度： $O(1)$

二分

显然在「朴素解法」中，我们没有利用「输入数组旋转前是一个“非递减排序”数组」的特性。

如果题目增加一个「元素各不相同」的限制，那么我们可以通过与 $array[0]$ 的关系进行「二分」。

以旋转点（最小值）为分割点的数组上，数组本身具有「二段性」：

旋转点（最小值）前面部分的数值满足 $>= array[0]$ ；
旋转点（最小值）后面部分的数值不满足 $>= array[0]$ 。

但本题不确保元素各不相同，这意味着我们无法直接根据与 $array[0]$ 的大小关系，将数组划分为两段，即无法通过「二分」来找到旋转点。

因为「二分」的本质是二段性，并非单调性。只要一段满足某个性质，另外一段不满足某个性质，就可以用「二分」。

举个🌰，我们使用数据 [0,1,2,2,2,3,4,5] 来理解为什么不同的旋转点会导致「二段性丢失」：

因此，我们需要处理掉那种「丢失二段性」的情况，再进行二分。

具体的，我们可以在「二分」前，检查二分起始右端点 r 与 $array[0]$ 的关系，如果相同，则将 r 左移。

代码：

import java.util.ArrayList;
public class Solution {
    public int minNumberInRotateArray(int [] array) {
        int n = array.length;
        int l = 0, r = n - 1;
        // 恢复二段性
        while (l < r && array[r] == array[0]) r--;
        // 二分找最小值
        while (l < r) {
            int mid = l + r + 1 >> 1;
            if (array[mid] >= array[0]) l = mid;
            else r = mid - 1;
        }
        return r + 1 < n ? array[r + 1] : array[0];
    }
}

时间复杂度：在恢复二段性的处理中，最坏情况下会遍历整个数组，复杂度为 $O(n)$ ；利用二段性找分割点的复杂度为 $O(\log{n})$ 。整体复杂度为 $O(n)$
空间复杂度： $O(1)$

最后

这是我们「剑指の精选」系列文章的第 No.6 篇，系列开始于 2021/07/01。

该系列会将牛客网「剑指 Offer」中比较经典而又不过时的题目都讲一遍。

在提供追求「证明」&「思路」的同时，提供最为简洁的代码。

欢迎关注，交个朋友 (｀・ω・´)