Find Peak Element

Finding Peak Element Indices

Draw this out and you’ll see the pattern. A peak element is greater than its neighbors.

O(N) Solution

int findPeakElement(const vector<int> &num) {
    for(int i = 1; i < num.size(); i ++)
    {
        if(num[i] < num[i-1])
        {// <
            return i-1;
        }
    }
    return num.size()-1;
}

This walks through the array. When we find an element smaller than its predecessor, the predecessor must be a peak. If we never find such a case, the last element is our peak.

O(logN) Solution

Binary search works here.

int findPeakElement(const vector<int> &num) {
    int low = 0;
    int high = num.size()-1;
        
    while(low < high)
    {
        int mid1 = (low+high)/2;
        int mid2 = mid1+1;
        if(num[mid1] < num[mid2])
            low = mid2;
        else
            high = mid1;
    }
    return low;
}

The key insight: compare mid with mid+1. If mid+1 is larger, there must be a peak on the right side. If mid is larger, there must be a peak on the left side (including mid itself).

This halves our search space each time, giving us O(logN).

#binary-search #arrays