Most efficient way to search a sorted matrix?

Question

I have an assignment to write an algorithm (not in any particular language, just pseudo-code) that receives a matrix [size: M x N] that is sorted in a way that all of it's rows are sorted and all of it's columns are sorted individually, and finds a certain value within this matrix. I need to write the most time-efficient algorithm I can think of.

The matrix looks something like:

1  3  5
4  6  8
7  9 10

My idea is to start at the first row and last column and simply check the value, if it's bigger go down and if it's smaller than go left and keep doing so until the value is found or until the indexes are out of bounds (in case the value does not exist). This algorithm works at linear complexity O(m+n). I've been told that it's possible to do so with a logarithmic complexity. Is it possible? and if so, how?

Answer 1

Your matrix looks like this:

a ..... b ..... c
. .     . .     .
.   1   .   2   . 
.     . .     . .
d ..... e ..... f
. .     . .     .
.   3   .   4   .
.     . .     . .
g ..... h ..... i

and has following properties:

a,c,g < i  
a,b,d < e
b,c,e < f
d,e,g < h
e,f,h < i

So value in lowest-rigth most corner (eg. i) is always the biggest in whole matrix and this property is recursive if you divide matrix into 4 equal pieces.

So we could try to use binary search:

1. probe for value,
2. divide into pieces,
3. choose correct piece (somehow),
4. goto 1 with new piece.

Hence algorithm could look like this:

input: X - value to be searched
until found
 divide matrix into 4 equal pieces
 get e,f,h,i as shown on picture
 if (e or f or h or i) equals X then 
   return found
 if X < e then quarter := 1
 if X < f then quarter := 2
 if X < h then quarter := 3
 if X < i then quarter := 4
 if no quarter assigned then 
    return not_found
 make smaller matrix from chosen quarter 

This looks for me like a O(log n) where n is number of elements in matrix. It is kind of binary search but in two dimensions. I cannot prove it formally but resembles typical binary search.