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?
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