Find Peak Element in Array - Optimal Binary Search Approach

Arrays - Binary Search

Contents

VisualizationProblemExamplesSolutionAlgorithmCodeTimeSpace

Visualization Player

Problem Statement❯

Given an array of integers, your task is to find the index of any peak element in the array.

A peak element is defined as an element that is not smaller than its neighbors. For the edge elements (first or last), we only compare with their one existing neighbor.

If there are multiple peaks, return the index of any one of them. If the array is empty, return -1.

Examples❯

Input Array Peak Index Peak Value Description
[1, 3, 20, 4, 1] 2 20 20 is greater than both 3 and 4, so it's a peak
[10, 20, 15, 2, 23, 90, 67] 1 or 5 20 or 90 Both 20 and 90 are peaks; either is valid
[5, 10, 20] 2 20 Last element is greater than its left neighbor
[20, 10, 5] 0 20 First element is greater than its right neighbor
[10] 0 10 Single element is always a peak
[1, 2] 1 2 Last element is greater than its only neighbor
[2, 1] 0 2 First element is greater than its only neighbor
[] -1 - Empty array, no peak exists

Solution❯

Understanding the Problem

A peak element in an array is one that is not smaller than its neighbors. That means at index i, the value arr[i] is a peak if it satisfies one of the following conditions:

  • It is the first element and arr[0] ≥ arr[1]
  • It is the last element and arr[n-1] ≥ arr[n-2]
  • It is in the middle and arr[i] ≥ arr[i-1] and arr[i] ≥ arr[i+1]

The goal is to efficiently find any one peak. Note: multiple peaks may exist, but we only need to find one of them.

Step-by-Step Solution with Example

Step 1: Start with an example

Let’s take the array [1, 3, 20, 4, 1, 0]. Visually, it looks like:

Index:   0   1   2   3   4   5
Value:   1   3  20   4   1   0

Here, 20 at index 2 is clearly greater than both 3 and 4, so it's a peak.

Step 2: Use Binary Search for Efficiency

We don’t need to linearly scan the entire array. A binary search approach gives us O(log n) efficiency:

  1. Set low = 0, high = n - 1
  2. While low ≤ high:
    • Compute mid = (low + high) / 2
    • Check if arr[mid] is a peak
    • If arr[mid] < arr[mid + 1], search the right half
    • Else if arr[mid] < arr[mid - 1], search the left half
    • Else return mid as the peak

Step 3: Apply Binary Search to Our Example

  • Initial range: low = 0, high = 5
  • mid = 2 → arr[2] = 20
  • Check neighbors: arr[1] = 3 and arr[3] = 4
  • 20 ≥ 3 and 20 ≥ 4 → it's a peak!

So, index 2 is returned. No further searching is needed.

Edge Cases

Case 1: Array has only one element

Example: [7] — This is automatically a peak as it has no neighbors.

Case 2: Peak is at the beginning

Example: [10, 5, 2] — Here, 10 ≥ 5, so index 0 is a peak.

Case 3: Peak is at the end

Example: [1, 2, 4] — 4 ≥ 2, so index 2 is a peak.

Case 4: Empty array

If arr.length == 0, there's no element to evaluate. We should return -1 to indicate no peak.

Finally

By understanding the definition of a peak and applying a smart binary search strategy, we can find any one peak efficiently in O(log n) time. Always check edge cases like an empty array, a single-element array, or peaks at the boundaries to make your solution robust.

And remember: we don’t need to find the highest peak — just any one that satisfies the peak condition!

Algorithm Steps❯

  1. Initialize low = 0 and high = n - 1.
  2. While low ≤ high, calculate mid = (low + high) / 2.
  3. Check if arr[mid] is a peak:
    • It is greater than or equal to its neighbors (consider edge conditions).
  4. If it is a peak, return mid.
  5. If arr[mid] < arr[mid + 1], move to right half: low = mid + 1.
  6. Else, move to left half: high = mid - 1.

Code

C
C++
Python
Java
JS
Go
Rust
Kotlin
Swift
TS
#include <stdio.h>

int findPeakElement(int arr[], int n) {
    int low = 0, high = n - 1;

    while (low <= high) {
        int mid = low + (high - low) / 2;
        int leftOK = (mid == 0 || arr[mid] >= arr[mid - 1]);
        int rightOK = (mid == n - 1 || arr[mid] >= arr[mid + 1]);

        if (leftOK && rightOK) return mid;
        else if (mid < n - 1 && arr[mid] < arr[mid + 1]) low = mid + 1;
        else high = mid - 1;
    }
    return -1;
}

int main() {
    int arr[] = {1, 3, 20, 4, 1, 0};
    int n = sizeof(arr) / sizeof(arr[0]);
    int peakIndex = findPeakElement(arr, n);
    printf("Peak Index: %d, Peak Element: %d\n", peakIndex, arr[peakIndex]);
    return 0;
}

Time Complexity❯

CaseTime ComplexityExplanation
Best CaseO(1)The middle element is a peak in the first check.
Average CaseO(log n)At each step, the search space is halved, similar to binary search.
Worst CaseO(log n)In the worst case, binary search continues until the peak is found at the edge.

Space Complexity❯

O(1)

Explanation: The algorithm uses constant extra space regardless of input size.

Problem Statement❯

Given an array of integers, your task is to find the index of any peak element in the array.

A peak element is defined as an element that is not smaller than its neighbors. For the edge elements (first or last), we only compare with their one existing neighbor.

If there are multiple peaks, return the index of any one of them. If the array is empty, return -1.

Examples❯

Input Array Peak Index Peak Value Description
[1, 3, 20, 4, 1] 2 20 20 is greater than both 3 and 4, so it's a peak
[10, 20, 15, 2, 23, 90, 67] 1 or 5 20 or 90 Both 20 and 90 are peaks; either is valid
[5, 10, 20] 2 20 Last element is greater than its left neighbor
[20, 10, 5] 0 20 First element is greater than its right neighbor
[10] 0 10 Single element is always a peak
[1, 2] 1 2 Last element is greater than its only neighbor
[2, 1] 0 2 First element is greater than its only neighbor
[] -1 - Empty array, no peak exists

Solution❯

Understanding the Problem

A peak element in an array is one that is not smaller than its neighbors. That means at index i, the value arr[i] is a peak if it satisfies one of the following conditions:

  • It is the first element and arr[0] ≥ arr[1]
  • It is the last element and arr[n-1] ≥ arr[n-2]
  • It is in the middle and arr[i] ≥ arr[i-1] and arr[i] ≥ arr[i+1]

The goal is to efficiently find any one peak. Note: multiple peaks may exist, but we only need to find one of them.

Step-by-Step Solution with Example

Step 1: Start with an example

Let’s take the array [1, 3, 20, 4, 1, 0]. Visually, it looks like:

Index:   0   1   2   3   4   5
Value:   1   3  20   4   1   0

Here, 20 at index 2 is clearly greater than both 3 and 4, so it's a peak.

Step 2: Use Binary Search for Efficiency

We don’t need to linearly scan the entire array. A binary search approach gives us O(log n) efficiency:

  1. Set low = 0, high = n - 1
  2. While low ≤ high:
    • Compute mid = (low + high) / 2
    • Check if arr[mid] is a peak
    • If arr[mid] < arr[mid + 1], search the right half
    • Else if arr[mid] < arr[mid - 1], search the left half
    • Else return mid as the peak

Step 3: Apply Binary Search to Our Example

  • Initial range: low = 0, high = 5
  • mid = 2 → arr[2] = 20
  • Check neighbors: arr[1] = 3 and arr[3] = 4
  • 20 ≥ 3 and 20 ≥ 4 → it's a peak!

So, index 2 is returned. No further searching is needed.

Edge Cases

Case 1: Array has only one element

Example: [7] — This is automatically a peak as it has no neighbors.

Case 2: Peak is at the beginning

Example: [10, 5, 2] — Here, 10 ≥ 5, so index 0 is a peak.

Case 3: Peak is at the end

Example: [1, 2, 4] — 4 ≥ 2, so index 2 is a peak.

Case 4: Empty array

If arr.length == 0, there's no element to evaluate. We should return -1 to indicate no peak.

Finally

By understanding the definition of a peak and applying a smart binary search strategy, we can find any one peak efficiently in O(log n) time. Always check edge cases like an empty array, a single-element array, or peaks at the boundaries to make your solution robust.

And remember: we don’t need to find the highest peak — just any one that satisfies the peak condition!

Algorithm Steps❯

  1. Initialize low = 0 and high = n - 1.
  2. While low ≤ high, calculate mid = (low + high) / 2.
  3. Check if arr[mid] is a peak:
    • It is greater than or equal to its neighbors (consider edge conditions).
  4. If it is a peak, return mid.
  5. If arr[mid] < arr[mid + 1], move to right half: low = mid + 1.
  6. Else, move to left half: high = mid - 1.

Code

C
C++
Python
Java
JS
Go
Rust
Kotlin
Swift
TS
#include <stdio.h>

int findPeakElement(int arr[], int n) {
    int low = 0, high = n - 1;

    while (low <= high) {
        int mid = low + (high - low) / 2;
        int leftOK = (mid == 0 || arr[mid] >= arr[mid - 1]);
        int rightOK = (mid == n - 1 || arr[mid] >= arr[mid + 1]);

        if (leftOK && rightOK) return mid;
        else if (mid < n - 1 && arr[mid] < arr[mid + 1]) low = mid + 1;
        else high = mid - 1;
    }
    return -1;
}

int main() {
    int arr[] = {1, 3, 20, 4, 1, 0};
    int n = sizeof(arr) / sizeof(arr[0]);
    int peakIndex = findPeakElement(arr, n);
    printf("Peak Index: %d, Peak Element: %d\n", peakIndex, arr[peakIndex]);
    return 0;
}

Time Complexity❯

CaseTime ComplexityExplanation
Best CaseO(1)The middle element is a peak in the first check.
Average CaseO(log n)At each step, the search space is halved, similar to binary search.
Worst CaseO(log n)In the worst case, binary search continues until the peak is found at the edge.

Space Complexity❯

O(1)

Explanation: The algorithm uses constant extra space regardless of input size.


Comments

💬 Please keep your comment relevant and respectful. Avoid spamming, offensive language, or posting promotional/backlink content.
All comments are subject to moderation before being published.

Loading comments...