Find a Peak Element in Array

Question:

A peak element in an integer array is defined as an element that is greater than its neighbors.

Given an input array where num[i] ≠ num[i+1], find a peak element and return its index.
The array may contain multiple peaks, in that case return the index to any one of the peaks is fine.
You may imagine that num[-1] = num[n] = -∞.
For example, in array [2, 4, 8, 3], 8 is a peak element and your function should return the index number 2.

Solution:

This problem can be solved as a search problem and we can use binary search method to look for the peak element.

public class Solution {
    public int findPeakElement(int[] num) {
        return findPeak(num,0,num.length-1);
    }
    
    public int findPeak(int[] num, int start, int end){
        if(start > end){
            return -1;
        }
        int mid = start + (end-start)/2;
        if( (mid+1 ==num.length || num[mid] > num[mid+1]) && ( mid==0 || num[mid]>num[mid-1]) ){
            return mid;
        }else if(mid-1>=0 && num[mid-1] > num[mid]){
            return findPeak(num,start,mid-1);
        }else{
            return findPeak(num,mid+1,end);
        }
        
    }
}

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>

Post Navigation