We can adapt Words Like Jared’s answer, by looking at how it can go wrong.
The idea in that answer — which is a good one — is to “roll downhill”. This just means, if you are on an element, check if it is a local minimum. If so, you are done; otherwise, step to the smallest of its nearest neighbors. Eventually this must terminate because every step is to a smaller element, and that cannot go on forever in a finite array.
The problem with this approach is that the “rolling” can meander all over the place:
20 100 12 11 10 100 2
19 100 13 100 9 100 3
18 100 14 100 8 100 4
17 16 15 100 7 6 5
If you start at the upper left and “roll downhill”, you will visit around half of the elements in the array. That is too many, so we have to constrain it a bit.
Start by examining the middle column and middle row. Find the smallest element among all of those and start there.
Roll one step “downhill” from there to enter one of the four quadrants. You will enter one of the quadrants, because the adjacent elements in the middle column and/or row are larger, so only one of the two adjacent quadrants could be “downhill”.
Now consider what would happen if you “rolled downhill” from there. Obviously, you would eventually reach a local minimum. (We will not actually do this because it would take too long.) But, in the course of rolling around, you would never leave that quadrant… Because to do so, you would have to cross either the middle column or middle row, and none of those elements are smaller than where you started. Therefore that quadrant contains a local minimum somewhere.
Thus, in linear time, we have identified a quadrant that must contain a local minimum, and we have cut n in half. Now just recurse.
This algorithm takes time 2n + 2n/2 + 2n/4 + …, which equals 4n, which is O(n) so we are done.
Interestingly, we did not use “rolling downhill” very much at all, except for the critical part: Proving that the algorithm works.
[Update]
As Incassator points out, this answer is not entirely correct, because after you “just recurse” you might roll out of the quadrant again…
The simplest fix is to find the smallest element among the middle row, middle column, and boundary before you “roll downhill”.