You need to search for a given number in an n n matrix in w

You need to search for a given number in an n × n matrix in which every row and every column is sorted in increasing order. Can you design a O(n) algorithm for this problem? [Laa10]

Solution

Algorithm FindKeyInNxNMatrix(Array[1..n, 1..n], key)

for(i := 1 to n)

if(Array[i, i] >= key)

break;

if(Array[i, i] == key)

return true;

else if(Array[i, i] < key)

for(j = i+1; i <= n; j++)

if(Array[i, j] == key)

return true;

return false;

else

for(j = 0; j < i; j++)

if(Array[i, j] == key)

return true;

return false;