二分法的二段性 二分法的二段性

传统的二分查找是在顺序储存结构中的一种高效的查找方法。但是，二分法的应用并不一定只能在顺序储存结构（单调性）中体现。只要证明具有二段性，二分法就有用武之地。

Q162. 寻找峰值

题目中提示时间复杂度为O（logn)，有着强烈的暗示这是个二分法。但是细看nums数组并不是单调排列，这给我们带来了疑惑。

接下来我们对这道题目二分法的合法性进行证明。

对于nums[i]，如果nums[i-1]>nums[i]，则在nums[i]左侧必有峰，如果nums[i]<nums[i+1],则在nums[i]右侧必有峰。

证明：

1. 如果数组严格单调，对于nums[i-1]>nums[i]，峰会出现在左侧nums[0]处（nums[-1]=负无穷），如果nums[i]<nums[i+1]，峰值会出现在右侧nums[n-1]处。（nums[n]=负无穷）。
2. 如果数组不是严格单调，对于nums[i-1]>nums[i]，其左侧必存在nums[j]>nums[j-1] (j<i)，必定在i左侧存在峰，同理，右侧也一样。

由此，我们证明了二分法的合理性。

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

总结

由此题我们可以得知，二分法的奥义（本质）不在于单调性，而是二段性。