A peak in a 1-D array is simply an element which has left and right elements smaller than it.

1, 3, 4 ,6 ,9, 11, **14**, 12, 7, 3, 2

14, clearly is peak here.

A straight forward algorithm would be to parse the array from left to right and keep checking if a[index]>=a[index+1] and a[index]>a[index-1], we have found a peak.

The above algorithm gives me a complexity of O(N).

An improvement over above approach to user divide and conquer approach, like we do in binary search.

1. Go to mid of the array Arr[N/2]

2. Check if it is peak (left and right are smaller)

3. check if left element is larger than mid element, if yes, NewArr= Arr[0..N/2-1]

4. else NewArr=Arr[N/2+1..N]

5. Repeat from 1 with NewArr

Complexity

T(N)=T(N/2)+C //at every step we will divide the array into 2, C is constant time taken in the opertaion

=T(N/4)+C+C

=T(N/8)+C+C+C

=T(N/2^k)+CK

… total number of steps is lg(N)

=T(1)+C*lg(N)

or O(lgN) complexity.