Given an array of \(N\) elements, return the second maximum/minimum elements using minimum number of comparison. A standard way for this task is to apply a tree and keep track of a list of compared items. However, it is important to realize that this optimal is achieved only when the elements are distinct. Otherwise, one can end up comparing an extra half of the whole array. For example, to locate the second minimum of the following array:

Read more

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.

Read more