Find a peak element in a 2D array

https://www.geeksforgeeks.org/find-peak-element-2d-array/
https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-006-introduction-to-algorithms-fall-2011/lecture-videos/MIT6_006F11_lec01.pdf

Alg:

Method 2 : (Efficient)
This problem is mainly an extension of Find a peak element in 1D array. We apply similar Binary Search based solution here.

1. Consider mid column and find maximum element in it.
2. Let index of mid column be ‘mid’, value of maximum element in mid column be ‘max’ and maximum element be at ‘mat[max_index][mid]’.
3. If max >= A[max_index][mid-1] & max >= A[max_index][mid+1], max is a peak, return max.
4. If max < mat[max_index][mid-1], recur for left half of matrix.
5. If max < mat[max_index][mid+1], recur for right half of matrix.

Time Complexity : O(rows * log(columns)). We recur for half number of columns. In every recursive call we linearly search for maximum in current mid column.

Auxiliary Space : O(columns/2) for Recursion Call Stack