question to data structure algorithm?

Question

The input is an N by N matrix of numbers that is already in memory. Each individual row is increasing from left to right. Each individual column is increasing form top to bottom. Give an O(N) worst-case algorithm that decides if a number X is in the matrix.

Answer 1

If you mean that the increment is by 1 between successive rows and columns, call the first entry in the upper left hand corner k. Now the last number (call it m) in the lower right-hand entry is k+2(N-1). All you have to do is compute m and check k ≤ X ≤ m and you're done.

If you mean that the numbers are increasing by one between successive columns and the next row begins with a value that is N greater that the previous row (also called 'lexigraphic order' for the obvious reason) it becomes m = k+(N²-1) and you do the same thing.


Doug

Answer 2

Let it be A[i,j]
The psedo code logic
let us check for num

for ( i = 1 to N by 1)
if(A[i,1] <= num /* if it is more we need not consider
for k = 1 to N by 1
if(A[i,k] > num go to outer loop
if A[i , K] = num exit found
endfor
else exitloop not found
endif