2D peak reasoning to move to a half You have a 2D integer matrix given. An element is a peak element if it is greater than or equal to its four neighbors, left, right, top and bottom. For example neighbors for A[i][j] are A[i-1][j], A[i+1][j], A[i][j-1] and A[i][j+1]. For corner elements, missing neighbors are considered of negative infinite value.

If someone has any understanding please share on how it decides which side to pick as that reduces complexity to $O(n \log n)$. 

Solution is to consider the middle column, find its 1d maximum, then if it's not the peak, look at left and right side and pick a side which is larger. My doubt is, why is this algorithm correct? 



Related material:

A) geeks link: 
https://www.geeksforgeeks.org/find-peak-element-2d-array/

B) mit 
This was shared in mit slides where it talks about 1d peak and then 2d peak 
1)  https://courses.csail.mit.edu/6.006/spring11/lectures/lec02.pdf

2) its second link gives an working example but not the reasoning 
http://courses.csail.mit.edu/6.006/fall11/lectures/lecture1.pdf
shows a working 

C) Stackoverflow 
There is also a StackOverflow discussion 
https://stackoverflow.com/questions/23120300/2d-peak-finding-algorithm-in-on-worst-case-time

My doubt is How Can it predict based on seeing left and right element accurately that it has to go to the bigger half. I tried it a lot of times and it always works. So  I know it to be true. I then tried to create a counter example but I couldn't . 

It's a very old question : 
I initiated a chat but it didnt helped so asking question here : https://chat.stackoverflow.com/rooms/192196/2d-peak
The point is that we are not trying to find the global maximum element of the array, only a peak (that is, a local maximum). 

Let's say that you look at the middle column and find its global maximum, and this maximum is not a peak, because the value to its left is larger. Then you know that the left half of the matrix contains a value that is larger than all of the elements of the middle column. Hence there is always a peak in the left half (for example, the global maximum of the left half, but we do not necessarily search for that). 

The values in the right half are irrelevant; they could be larger or smaller, but we don't care. We only want to be sure that we do not recurse into a half that contains 0 peaks.