求局部最大值

声明： 本总结仅为个人学习总结，以防止遗忘而作，不得转载和商用。
问题描述:
给定一个无重复 元素的数组 A[0…N−1]，求找到一个 该数组的局部最大值。规定：在数组边界外的值无穷小。即： A[0]＞A[−1]，A[N−1]＞A[N]。
显然，遍历一遍可以找到全局最大值，而全局最大值显然是局部最大值，但是时间复杂度达到 O(n)，能不能找到一个时间复杂度比 O(n) 还要低的解法呢？
问题分析:
定义：若子数组 Array[from,…,to] 满足
Array[from]＞Array[from−1]
Array[to]＞Array[to+1]
我们假定称该子数组为“高原数组”。（高原数组这个词是我们自创的，为了形象说明）
若高原数组长度为1，则该高原数组的元素为局部最大值。
算法描述
使用索引 left、right 分别指向数组首尾，根据定义（比两边都高），该数组为高原数组。
求中点 mid=(left+right)/2，若A[mid]＞A[mid+1]，子数组 A[left…mid] 为高原数组。
丢弃后半段并且使得 right=mid
若 A[mid+1]＞A[mid]，子数组 A[mid…right] 高原数组。
丢弃前半段，left=mid+1，递归直至 left==right
时间复杂度为 O(logN)

Java版本实现：

public static int localMaximun(int[] a){
        int left = 0;
        int right = a.length-1;
        int mid;
        while (right>left) {
            mid = (left+right)/2;
            if (a[mid]>a[mid+1]) {
                right = mid;
            }else {
                left = mid+1;
            }
        }
        return a[left];
    }

测试代码：

        int a[] = {3,5,1,2,3,7,14,8};
        System.out.println(localMaximun(a));

输出结果：14