You are given an 2D array of MxN which is row and column wise sorted. What is the efficient way to search for an element?
Steps:
1) Start from top right element
2) for loop compare this element e with x
a) if they are equal then return its position
b) e < x then go down c) e > x then go to left
3) return false if limits go out of bound.
Implementation:
int search(int mat[4][4], int M, int N, int elem) { int row = 0; int col = N-1; while (row < M && col >= 0) { if (mat[row][col] == elem) { return 1; } else if (mat[row][col] > elem) { col--; } else { row++; } } return 0; }
Time Complexity: O(n)
You could also use a binary search using a pointer that fakes a one dimensional array using the subscripts, like this:
// int *ptr = mat[ 0 ];.
because..
mat[ row ][ col ] = ptr[ row * columnSize + col ].