Find Peak Element in 2D Matrix Using Binary Search in C

A peak element in a 2D matrix is an element that is greater than or equal to its neighbors (up, down, left, right).

Instead of checking every element, we can use a binary search approach on columns to optimize the solution.

This reduces time complexity significantly compared to brute force.

Concept Overview

In 2D arrays, a peak element satisfies local maximum conditions.

Binary search can be applied on columns instead of rows.

At each step, we find the maximum element in a column.

Problem Statement

Given a 2D matrix, find the position of any peak element.

Example

Input:
Matrix:
10 20 15
21 30 14
7 16 32

Output:
Peak Element: 30 (or 32)

Approach (Column-wise Binary Search)

1. Select middle column.

2. Find the row index of maximum element in that column.

3. Compare with left and right neighbors.

4. If it is a peak, return it.

5. If left neighbor is greater, move left.

6. If right neighbor is greater, move right.

7. Repeat until peak is found.

C Program

#include <stdio.h>

#define ROWS 3
#define COLS 3

int findMaxInColumn(int mat[ROWS][COLS], int col) {
    int maxRow = 0;
    for (int i = 1; i < ROWS; i++) {
        if (mat[i][col] > mat[maxRow][col])
            maxRow = i;
    }
    return maxRow;
}

void findPeak(int mat[ROWS][COLS]) {
    int low = 0, high = COLS - 1;

    while (low <= high) {
        int mid = (low + high) / 2;
        int maxRow = findMaxInColumn(mat, mid);

        int left = (mid - 1 >= 0) ? mat[maxRow][mid - 1] : -1;
        int right = (mid + 1 < COLS) ? mat[maxRow][mid + 1] : -1;

        if (mat[maxRow][mid] >= left && mat[maxRow][mid] >= right) {
            printf("Peak Element: %d at (%d, %d)", mat[maxRow][mid], maxRow, mid);
            return;
        }
        else if (left > mat[maxRow][mid]) {
            high = mid - 1;
        }
        else {
            low = mid + 1;
        }
    }
}

int main() {
    int mat[ROWS][COLS] = {
        {10, 20, 15},
        {21, 30, 14},
        {7, 16, 32}
    };

    findPeak(mat);
    return 0;
}

Output

Peak Element: 30 at (1, 1)

Detailed Explanation

The algorithm reduces the search space by focusing on columns.

At each step, it selects the maximum element in the middle column.

Based on neighbor comparison, it decides the direction.

This ensures logarithmic search in one dimension.

Time and Space Complexity

Time Complexity: O(n log m)

Space Complexity: O(1)

Applications

Used in image processing and peak detection systems.

Helpful in optimization problems and data analysis.

Advantages

Efficient compared to brute force O(n*m).

Uses binary search principles in 2D.

Limitations

More complex than 1D peak finding.

Requires careful boundary handling.

Improvements You Can Make

Extend to non-square matrices.

Find all peaks instead of one.

Apply divide-and-conquer optimization.

This problem is a great step toward mastering advanced multidimensional search algorithms.