CareerCup

divide and conquer?

Try searching from the top right corner...

Performing Binary Search on an sorted array would be the most efficient one...

Simple quaternary search should help, and you would get the answer in O(logN) time.

In case of a[m][n] matrix.
column = n; // start from last column.
row = 0; // start from first row.
while(row > n and column > 0)
{
if(a[i][j] == searchValue)
{
print row and column
return;
}
if (a[i][j] < searchValue)
{
//increase the row only.
}
else
{
// a[i][j] > searchValue
//decrease the column only.
}
}

Divide the matrix in four n/2 x n/2 matrices:
A B
C D

if n = 1, compare and print if equal
If n >= top left of A and n <= bottom right of A, search in A
if n >= top left of C and n <= bottom right of C, search in C
if n >= top left of B and n <= bottom right of B, search in B
else if n > bottom right of D exit
else search in D

Use Linear Step searching algorithm for this.
Start at the top right of the matrix.
If top right element is > target element then move left.
or else move down.
Keep doing this until we find the target.
Average case is O(n). If the element is at the bottom left then there are 2n steps

Use Linear Step searching algorithm for this.
Start at the top right of the matrix.
If top right element is > target element then move left.
or else move down.
Keep doing this until we find the target.
Average case is O(n). If the element is at the bottom left then there are 2n steps