Find Peak Element Using Binary Search in C

A peak element is an element that is greater than or equal to its neighbors.

This problem can be solved efficiently using binary search instead of a linear scan.

In this tutorial, we will implement an optimized solution in C.

Concept Overview

A peak element is any element that is not smaller than its adjacent elements.

There can be multiple peaks, and returning any one of them is valid.

Binary search helps reduce time complexity to O(log n).

Problem Statement

Given an array, find the index of any peak element.

Example

Input:
Array: 1 3 20 4 1 0

Output:
Peak Index: 2
Peak Element: 20

Approach (Binary Search)

1. Initialize low = 0 and high = n-1.

2. Find mid = (low + high) / 2.

3. If arr[mid] < arr[mid+1], peak lies on right side.

4. Else, peak lies on left side (including mid).

5. Repeat until low == high.

C Program

#include <stdio.h>

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

    while (low < high) {
        int mid = (low + high) / 2;

        if (arr[mid] < arr[mid + 1])
            low = mid + 1;
        else
            high = mid;
    }

    return low;
}

int main() {
    int arr[] = {1, 3, 20, 4, 1, 0};
    int n = sizeof(arr) / sizeof(arr[0]);

    int peakIndex = findPeak(arr, n);

    printf("Peak Index: %d\n", peakIndex);
    printf("Peak Element: %d", arr[peakIndex]);

    return 0;
}

Output

Peak Index: 2
Peak Element: 20

Detailed Explanation

The algorithm compares the middle element with its next neighbor.

If the next element is larger, the peak must be on the right side.

Otherwise, the peak lies on the left side or at mid.

This reduces the search space in each iteration.

Time and Space Complexity

Time Complexity: O(log n)

Space Complexity: O(1)

Applications

Used in signal processing and peak detection systems.

Helpful in optimization and search problems.

Advantages

Faster than linear search.

Efficient for large datasets.

Limitations

Does not guarantee the highest peak, only a local peak.

Improvements You Can Make

Modify to find all peak elements.

Extend to 2D arrays (matrix peak problem).

Combine with other search techniques.

Understanding peak finding helps you master binary search variations and optimization problems.