Finding a peak in 1 Dimensional Array

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.

Leave a Reply