高原数组 局部最大值

https://blog.csdn.net/weixin_41563161/article/details/101027801

题目


         给定一个无重复元素的数组A[0…N-1]，求找到一个该数组的局部最大值。

         规定：在数组边界外的值无穷小。

思想


         遍历一遍得全局最大值，它显然是局部最大值，但可否有更快的办法

         定义：若子数组Array[from,…,to] 满足Array[from]＞Array[from-1]且Array[to]＞Array[to+1]，则称该数组为“高原数组”。

         于是：如果from和to退化为一个点，那这个点就是局部极大值点。于是我们就不停的切切切把高原数组切成一个点。
 

算法描述

     

 

public class Test5 {
    public static void main(String[] args) {
        int[] a = {3,5,1,2,6,7,14};
        System.out.println(maxLocal(a));
    }
    public static int maxLocal(int[] a){
        int left = 0;
        int right = a.length - 1;
        int mid = 0;
        while (left < right){
            mid = (right + left) / 2;
            System.out.println(a[mid]);
            if(a[mid] > a[mid+1]){
                right = mid;
            }else {
                left = mid +1;
            }
        }
        return a[left];
    }
}

 

时间复杂度


         时间复杂度为O(logN)。

 

参考文献

https://segmentfault.com/a/1190000019838473