This algorithm to find peak element in an array, Peak element is an element which has greater value than its left and right element.
one way to get peak element is using linear search which takes O(n), but we can also search using binary algo.
Lets see algorithm directly.
Algorithm
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 |
package com.omt.learn.algo; /** * Created by omt on 3/23/17. */ public class FindPeakElmFromArray { public static void main(String args[]) { int a[] = {30,45,60,20,30,15,9,80}; //60, 30, 80 System.out.println(findOnePeakElement(a, 0, a.length-1)); } private static int findOnePeakElement(int a[], int start, int end) { while(start <= end) { int mid = (start+end)/2; if(mid-1 >= start && a[mid] < a[mid-1]) { end = mid-1; } else if(mid+1 <= end && a[mid] < a[mid+1]) { start = mid+1; } else { return a[mid]; } } return -1; } } |