An element in a multi-dimensional array is said to be a local minimum if it is greater -than- none of its neighbours.
In the one-dimensional case, a logarithmic solution is based on bisection (and advancing to the greater than the middle half).
2-dimensional
Let \(A\) be a \(N\times N\) matrix. Can one locate a local minimum within linear time?
The idea is to consider bisection and boundary search. First, locate the midpoint, which then divide the matrix into 4 sub-regions. Compute the minimum among the boundaries of these sub-regions. So, basically, we have three rows (the top, middle and the bottom) and three columns (left, middle and right) to consider.
- The minimum happens to be a local minimum, done.
- Otherwise, proceeds to the better region (one that contains a smaller neighbour).
- This sub-region has size reduced by half.
At the \(k\)-th time, we query at most \(6\times\text{region side}\) elements. This gives an \(O(N)\) algorithm.
\(n\)-dimensional
One can generalized the above algorithm to \(n\)-dimensional array. Similar analysis shows tthat the runtime is \(O(N^{n-1})\). Namely, we can just query a hyperplane to look for local minimum instead of the whole space.
Correctness
Let \(R_{n}\) be the region considered at the \(n\)-th step with \(R_{0}=\text{ initial region}\). Consider the sequence \(\left\{ a_{n}\right\} \) defined by \(a_{n}=\min\partial R_{n}\), where \(\partial R_{n}\) is the boundary of \(R_{n}\).
Note that every two consecutive boundaries contains at least a common point which is the global minimum of the boundary \(R_{n}\).
In other words, \(a_{n}\in\partial R_{n}\cap\partial R_{n+1}\) and hence \(a_{n+1}\leq a_{n}\). When one proceeds to the next region, \(R_{n+1}\), there exists a point \(p\) in its interior with \(p \lt a_{n}\).
Since the size of \(R_{n}\) is reduced by half, it eventually shrinks to a single point \(p^{*}\) satisfying \(p^{*}\leq a_{k}\) for all \(a_{k}\), which is a local minimum.
Demonstration Code
Below is a python code using numpy for the search detail: