Show Buttons
Share On Facebook
Share On Twitter
Share On Google Plus
Share On Linkdin
Share On Pinterest
Share On Reddit
Share On Stumbleupon
Contact us
Hide Buttons

Find a peak element in a Given Array

Objec­tive : In this arti­cle we will dis­cuss an algo­rithm to Find a peak ele­ment in a Given Array. We will see the recur­sion tech­niques to solve this problem.

Peak Ele­ment: peak ele­ment is the ele­ment which is greater than or equal to both of its neighbors.

Input:  Array, arrA[] .

Out­put: A peak ele­ment and its index

Approach:

A sim­ple approach is to do a lin­ear scan to a array and using few vari­ables we can find a peak ele­ment. But the Time Com­plex­ity will be O(n) but real ques­tion is, Can we do better?

The Answer is yes, by using Binary Search tech­niques.

  • If mid­dle ele­ment is the peak ele­ment, return it
  • If mid­dle ele­ment is smaller than its left ele­ment , we will get our peak ele­ment on the left half
  • If mid­dle ele­ment is the smaller than its right ele­ment, we will our peak ele­ment on the right.

Time Com­plex­ity : O(logN) 

Notes:

  1. If array has all the same ele­ments, every ele­ment is a peak element.
  2. Every array has a peak element.
  3. Array might have has many peak ele­ments but we are find­ing only one.
  4. If array is in ascend­ing or descend­ing order then last ele­ment or the first ele­ment of the array will be the peak ele­ment respectively.

Com­plete Code:


Out­put:

Peak Element is found at index [6] = 5

 

You may also like...