CareerCup

1.traverse 1st row:
if found, return;
else if (any a[0][i]>number) traverse i-1 column
if found return;
2.
traverse 1st column:
if found return;
else if(any a[i][0]>num)
traverse "i-1"th row: if found return;


time complexity :2(m+n) ie O(m+n);

Take each row of the 2D array and perform a binary search on each row.
Time Complexity: O(m log n) - where 'm' is the num of rows and 'n' is the num of columns

Algo... Time complexity O(N+M)
say matrix dim N, M.
start with i = 0, j = M-1.
Say no. to b searched is x.
then if(Mat[i][j] < x)
i++;
if(Mat[i][j] > x)
j--;
else {
printf("Element found");
return;
}
Keep on doing this till i == N or j < 0.

void search_element(int Mat[][], int N, int M, int x) {
int i = 0, j = M-1;
while(i > N && j >= 0) {
if(Mat[i][j] > x) 
j--;
else if(Mat[i][j] < x) 
i++;
else { 
printf("Element found, i = %d, j = %d\n", i, j);
return;
}
}

printf("Not Found\n");
}

Searching diagonal element is a good approach. My idea is as following:
(1) if data[0][0] < pattern, return false;
(2) while(index < sizeRow){
if (data[index][index] == pattern) return true;
if (data[index][index] > pattern) break;
index++;}
(3) if (index == sizeRow) return false;
else search data[index][0-index] and data[0-index][0]

Complexity is traversal diagonal element is O(N) and search column and Row is 2O(logN)
Total is O(N)

Given is the algo in java

public static void main(String[] args)
	{
		int[][] mat = {
				{1, 4, 7},
				{2, 5, 8},
				{3, 6, 9},
			};
		
		findNum(mat, 9);
	}

	private static void findNum(int[][] mat, int num)
	{
		int i = mat.length-1;
		int j = 0;
		for(;i>=0 && i<mat.length && j>=0 && j<mat[0].length;)
		{
			if(mat[i][j]==num)
			{
				System.out.println("Found: (" + i + ", " + j+")");
				return;
			}
			if(num>mat[i][j])
				j++;
			else
				i--;
		}
		System.out.println("Not Found");
	}

Start fro left upper corner:
if number is greater than [0][N] go down a row else go right(less coloumn) untill you find the number

Complexity: O(m+n) where m and n are number of rows and col
Please suggest improvments to algo

Start fro left upper corner:
if number is greater than [0][N] go down a row else go right(less coloumn) untill you find the number

Complexity: O(m+n) where m and n are number of rows and col
Please suggest improvments to algo

Late to the party.. What do you guys think about this? Using Binary search method

int main(){
	int sample[3][4] = {{1, 2, 3, 4}, {5, 6, 7, 8}, {9, 10, 11, 12}};
	int target = 6;
	int lowX, highX, lowY, highY, midX, midY;
	
	//Note: some values are hardcoded, should not matter.
	lowX = 0;
	highX = 2;
	lowY = 0;
	highY = 3;
	
	if(target <= sample[0][0] || target >= sample[3 - 1][4 - 1]){
		std::cout<<"Nope";
	}

	while(lowX <= highX && lowY <= highY){
		midX = (lowX + highX)/2;
		midY = (lowY + highY)/2;

		if(target < sample[midX][midY]){
			highX = midX - 1;
			highY = midY - 1;
		}
		else if(target > sample[midX][midY]){
			lowX = highX + 1;
			lowY = highY + 1;
		}
		else {
			lowX = highX + 1;
			lowY = highY + 1;
		}
	}

	if(target == sample[midX][midY]){
		std::cout<<"Found";
	}
	else{
		std::cout<<"Nope";
	}
	
	return 0;
}

search for the element in the diagonal.
its O(n) where n is the row length.