matrix

standard puzzle:

You are given a two dimensional array (say m*n) in which all the rows as well as the columns are sorted. Describe an efficient algorithm to discover if an element is present or not. what will be the computational time

e.g of the sorted matrix

10,15,18,20,24,
28,19,30,37,40,
46,48,49,59,60

click here for answer

call function(m/2, 0, search element,false);

// do binary search starting with value in middle row and first column
function(row number,col number, search element, bool first time){
if(matrix[row,col] == search element){
return true;
}
if(matrix[row,col]{
if(first time)
function(m+1,1,search element, false)
else
return functionbinarysearch((row*N + (row+1)*N)/2,row*N, (row+1)*2, search element)

}
else{
if(first time)
function(row-1,1,search element, false)
else
return functionbinarysearch((row*N + (row-1)*N)/2,(row-1)*2, row*N, search element)


}
//do binary search on one row
functionbinarysearch(middleIndex,first, last,search element){
if(! (middleindex>first && middle index return false;

if(matrix[index]==search element) return true;
else if( matrix[index] functionbinarysearch(middleIndex+last/2,middle, last,search element)
else
functionbinarysearch(middleIndex+first/2,first, middle,search element)
}

complexity: O(m+n)

ofcourse there could be other algo's and methods that yields better performance