Find a Peak Element

This one looks simple. Find a peak in an array. But the interviewer is not checking if you can scan a list. They want to see if you spot that binary search can work even when the array is not sorted. So the real test is this. Can you find the hidden structure that lets you throw away half the data each time?

🏔️ The Problem

A peak element is a value that is strictly greater than both of its neighbors. So the number on its left is smaller, and the number on its right is smaller too. Your job is to find any one peak and return its index.

One thing makes this easier. We pretend the edges of the array have negative infinity just outside them. So the first and last elements only need to beat their one real neighbor. That means an array always has at least one peak.

Here is an example.

Input:  [1, 2, 1, 3, 5, 6, 4]
Output: 5
Explanation: index 5 holds 6. And 6 is greater than 5 on its left and 4 on its right. So it is a peak.
(index 1 holding 2 is also a valid peak. Any peak is accepted.)

🐢 The Simple Approach First

The first idea everyone has is to just walk through the array. Check each element against its left and right neighbor. The moment you find one that beats both sides, you return it.

This works. But it looks at every element one by one. So in the worst case you touch all n items. That is O(n) time. In an interview that is the answer they expect you to start with. It is not the answer they want you to stop at.

So you say it out loud. Then you say: “but we can do better than linear time.” That line is what they are waiting for.

🧗 The Optimal Approach: Walk Uphill

Now the clever part. We will use binary search, which means we look at the middle and then throw away one half each time.

But wait. The array is not sorted. How can binary search work? Here is the idea. We do not search for a value. We follow the slope.

Look at the middle element. Compare it with its right neighbor.

• If the middle element is smaller than its right neighbor, then the ground is going up as we move right. So there has to be a peak somewhere on the right side. We move right.
• If the middle element is greater than or equal to its right neighbor, then the ground is going down to the right. So a peak sits on the left side, or the middle itself is the peak. We move left, and we keep the middle in our range.

See why this always works? You keep stepping toward higher ground. You are walking uphill. And the slope cannot rise forever, because the array ends. Just past the end we imagined negative infinity. So you must hit a top. That top is a peak.

Steps to find a peak

1. Set low to 0 and high to the last index.
2. While low is less than high, find mid as the middle of low and high.
3. If the element at mid is smaller than the element at mid + 1, a peak is on the right. So set low to mid + 1.
4. Otherwise a peak is on the left or at mid. So set high to mid.
5. When low equals high, that index is a peak. Return it.

#include <stdio.h>

// Returns the index of any peak element in O(log n).
int findPeakElement(int arr[], int n) {
    int low = 0, high = n - 1;
    while (low < high) {
        int mid = low + (high - low) / 2;
        // Ground rising to the right? A peak must be on the right.
        if (arr[mid] < arr[mid + 1]) {
            low = mid + 1;
        } else {
            // Ground falling or flat? Peak is left or at mid.
            high = mid;
        }
    }
    return low; // low == high here, and it points to a peak.
}

int main(void) {
    int arr[] = {1, 2, 1, 3, 5, 6, 4};
    int n = sizeof(arr) / sizeof(arr[0]);
    printf("Peak index: %d\n", findPeakElement(arr, n));
    return 0;
}

Peak index: 5

#include <iostream>
#include <vector>
using namespace std;

// Returns the index of any peak element in O(log n).
int findPeakElement(const vector<int>& arr) {
    int low = 0, high = arr.size() - 1;
    while (low < high) {
        int mid = low + (high - low) / 2;
        // Ground rising to the right? A peak must be on the right.
        if (arr[mid] < arr[mid + 1]) {
            low = mid + 1;
        } else {
            // Ground falling or flat? Peak is left or at mid.
            high = mid;
        }
    }
    return low; // low == high here, and it points to a peak.
}

int main() {
    vector<int> arr = {1, 2, 1, 3, 5, 6, 4};
    cout << "Peak index: " << findPeakElement(arr) << endl;
    return 0;
}

Peak index: 5

public class PeakElement {

    // Returns the index of any peak element in O(log n).
    static int findPeakElement(int[] arr) {
        int low = 0, high = arr.length - 1;
        while (low < high) {
            int mid = low + (high - low) / 2;
            // Ground rising to the right? A peak must be on the right.
            if (arr[mid] < arr[mid + 1]) {
                low = mid + 1;
            } else {
                // Ground falling or flat? Peak is left or at mid.
                high = mid;
            }
        }
        return low; // low == high here, and it points to a peak.
    }

    public static void main(String[] args) {
        int[] arr = {1, 2, 1, 3, 5, 6, 4};
        System.out.println("Peak index: " + findPeakElement(arr));
    }
}

Peak index: 5

# Returns the index of any peak element in O(log n).
def find_peak_element(arr):
    low, high = 0, len(arr) - 1
    while low < high:
        mid = low + (high - low) // 2
        # Ground rising to the right? A peak must be on the right.
        if arr[mid] < arr[mid + 1]:
            low = mid + 1
        else:
            # Ground falling or flat? Peak is left or at mid.
            high = mid
    return low  # low == high here, and it points to a peak.


arr = [1, 2, 1, 3, 5, 6, 4]
print("Peak index:", find_peak_element(arr))

Peak index: 5

// Returns the index of any peak element in O(log n).
function findPeakElement(arr) {
  let low = 0;
  let high = arr.length - 1;
  while (low < high) {
    const mid = low + Math.floor((high - low) / 2);
    // Ground rising to the right? A peak must be on the right.
    if (arr[mid] < arr[mid + 1]) {
      low = mid + 1;
    } else {
      // Ground falling or flat? Peak is left or at mid.
      high = mid;
    }
  }
  return low; // low === high here, and it points to a peak.
}

const arr = [1, 2, 1, 3, 5, 6, 4];
console.log("Peak index:", findPeakElement(arr));

Peak index: 5

⏱️ Time and Space Complexity

We never store extra data, so space stays tiny. The big win is in time. The simple scan checks every element. The binary search throws away half the array each step.

🧩 Key Takeaways

• ✅ A peak element is strictly greater than both neighbors. And the imagined negative infinity past the edges means a peak always exists.
• ✅ The simple scan is O(n). It is fine as a first answer, but say out loud that you can do better.
• ✅ Binary search works here even without a sorted array, because you follow the slope, not a value.
• ✅ If the middle is smaller than its right neighbor, go right. Otherwise go left or stay. You always walk uphill toward a peak.
• ✅ Time drops to O(log n) with O(1) extra space.

🚀 What’s Next?

• Binary Search
• Search in a Rotated Sorted Array