Efficiently searching for a value in an ordered matrix

Question

I have a matrix with increasing numbers in each row direction (to the right) and each column direction (downwards), and seek to find the location of a particular number in the matrix or at least the location of entry that is closest to it if the number is not in the matrix. What would be the most computationally efficient way of achieving this?

Answer 1

Binary search middle row, then recurse on lower left and upper right sub matrixes.

This is the best and last solution described in the link below: http://articles.leetcode.com/2010/10/searching-2d-sorted-matrix.html

Answer 2

Binary search is one typical solution for arrays. Your matrix is basically a fragmented array, but it's very simple to adopt the same logic.