Algorithms, Java

You are given an n-by-n grid of distinct numbers. A number is a local minimum if it is smaller than all its neighbors. (A neighbor of a number is one immediately above, below, to the left, or to the right. Most numbers have four neighbors; numbers on the side have three; the four corners have two.) Use the divide-and-conquer algorithm design paradigm to compute a local minimum with only O(n) comparisons between pairs of numbers. (Note: since there are n^2 numbers in the input, you cannot afford to look at all of them.)

[Hint: Figure out how to recurse on an (n/2)-by-(n/2) grid after doing only O(n) work.]