24 高原数组 局部最大值

                             高原数组 局部最大值

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