CareerCup

let the array be of size mxn,

int i=0, j=n-1;
while(i<m && j>=0){
  if(arr[i][j]==num)
    print("number found at:", i + ":" + j);
  if(arr[i][j]>num)
    j--;
  if(arr[i][j]<num)
    i++;
}
}

binarySearch on 2D matrix:


#include <stdio.h>
#include <stdlib.h>

int rows = 50;
int cols = 50;

int** matrix = NULL;

int search_matrix(int start_row, int start_col, int end_row, int end_col,
int search_term) {

int returnValue = -1;

int mid_row = (start_row + end_row) / 2;
int mid_col = (start_col + end_col) / 2;

if (start_row > end_row || start_col > end_col || end_row < start_row
|| end_col < start_col || search_term < matrix[0][0])
return -1;

if (matrix[mid_row][mid_col] == search_term) {
printf("\nFound %d at Row = %d Column = %d\n", search_term, mid_row,
mid_col);
return mid_row;
}

if (matrix[mid_row][start_col] <= search_term
&& matrix[mid_row][cols] >= search_term) {
// we have found our row

if (matrix[mid_row][start_col] <= search_term
&& matrix[mid_row][mid_col] >= search_term) {
start_row = mid_row;
//start_col = 0;
end_row = mid_row;
end_col = mid_col;
}

else if (matrix[mid_row][mid_col] < search_term
&& matrix[mid_row][cols] >= search_term) {
start_row = mid_row;
start_col = mid_col;
end_row = mid_row;
end_col = cols;
}

returnValue = search_matrix(start_row, start_col, end_row, end_col,
search_term);

} else if (matrix[mid_row][0] > search_term) {
end_row = mid_row;
end_col = cols;

start_row = 0;
//start_col = 0;

returnValue = search_matrix(start_row, start_col, end_row, end_col,
search_term);

} else if (matrix[mid_row][0] < search_term) {

start_row = mid_row + 1;
//start_col = 0;

end_row = rows;
end_col = cols;

returnValue = search_matrix(start_row, start_col, end_row, end_col,
search_term);
}

return returnValue;
}

int main(int argc, char** argv) {

int i = 0, j = 0, counter = 0;

matrix = (int**) malloc(sizeof(int) * rows);
for (i = 0; i < rows; i++) {
matrix[i] = (int*) malloc(sizeof(int) * cols);
}

// initialize matrix
for (i = 0; i < rows; i++) {
for (j = 0; j < cols; j++)
matrix[i][j] = counter + j;

counter = matrix[i][cols - 1] + 1;
}

for (i = 0; i < rows; i++) {
for (j = 0; j < cols; j++)
printf("%d ", matrix[i][j]);

printf("\n");
}

cols = cols - 1;
rows = rows - 1;
int searchTerm = 2423;

int index = search_matrix(0, 0, rows, cols, searchTerm);

if (index == -1)
printf("\n%d not present in matrix\n", searchTerm);

return EXIT_SUCCESS;
}

@manikantansubramanyam: the above code is o(m+n). Actually, it will take m+n steps in the worst case.

This question is explained in detail in Cracking the Code Interview

Hey....

Use Binary Search Algorithm modified for 2D Array. It will work at O(log n), for an array of mxn or nxm, where n>m.

Pseudo code according to me:
tuple (x,y) = (0,0).
tuple (m,n) = (m,n)
then check if a[0][m/2] > num and [n/2][0] >num
decide accordingly and change the tuples correspondingly .
recursively search.

basically my logic is to half the matrix in each recursive call.

here is a good solution.

puddleofriddles.blogspot.com/2011/07/given-matrix-in-which-each-row-and-each.html

This is log(n) algorithm:

First we want to locate the row(may be one or two such row exists) at which our target number locate by applying Binary Search for the last column.(log(n))

Second, apply Binary Search for that row to locate our target number.(log(n))

A O(log(n)) solution:

int binarySearch(int n, vector<int> &A, int s, int e) {
	if(s >= e) return s;
	
	auto m = (s + e) / 2;
	auto v = A[m];
	if(v == n) return m;
	
	if(v < n) return binarySearch(n, A, m + 1, e);
	return binarySearch(n, A, s, m - 1);
}
struct Point {int i; int j; Point(int i_, int j_){i=i_;j=j_;}};
Point find(int n, vector<vector<int>> &A) {
	auto size = A.size();
	int row = 0, col = 0, prevCol = 0, prevRow = 0;
	while(A[row][col] < n) {
		if(A[row][size-1] >= n) {
			col = binarySearch(n, A[row], col, size - 1); //find the cell just less than the search value in the current row
			if(A[row][col] > n) { //binary search returned the higher cell, so decrement by 1
				col--;
			}
		}
		if(A[size - 1][col] >= n) {
			vector<int> column;
			for(auto r = row; r < size; r++) {
				column.push_back(A[r][col]);
			}
			row = binarySearch(n, column, 0, size - 1 - row) + row;//find the cell just less than the search value in the current column
			if(A[row][col] > n) {//binary search returned the higher cell, so decrement by 1
				row--;
			}
		}
		if(col == prevCol && row == prevRow) {//no movement -> not found
			break;
		}
		prevRow = row; prevCol = col;
	}  
	if(A[row][col] != n) return Point(-1, -1);
	return Point(row, col);
}

The comments made it less readable. Here a version with the comments

int binarySearch(int n, vector<int> &A, int s, int e) {
	if(s >= e) return s;
	
	auto m = (s + e) / 2;
	auto v = A[m];
	if(v == n) return m;
	
	if(v < n) return binarySearch(n, A, m + 1, e);
	return binarySearch(n, A, s, m - 1);
}
struct Point {int i; int j; Point(int i_, int j_){i=i_;j=j_;}};
Point find(int n, vector<vector<int>> &A) {
	auto size = A.size();
	int row = 0, col = 0, prevCol = 0, prevRow = 0;
	while(A[row][col] < n) {
		if(A[row][size-1] >= n) {
			col = binarySearch(n, A[row], col, size - 1); 
			if(A[row][col] > n) { 
				col--;
			}
		}
		if(A[size - 1][col] >= n) {
			vector<int> column;
			for(auto r = row; r < size; r++) {
				column.push_back(A[r][col]);
			}
			row = binarySearch(n, column, 0, size - 1 - row) + row;
			if(A[row][col] > n) {
				row--;
			}
		}
		if(col == prevCol && row == prevRow) {
			break;
		}
		prevRow = row; prevCol = col;
	}  
	if(A[row][col] != n) return Point(-1, -1);
	return Point(row, col);
}