CareerCup

The solution is here, rather, inverted.
geeksforgeeks.org/search-in-row-wise-and-column-wise-sorted-matrix/

This can be solved by modifying binary search.

One way could be start processing from the center of the matrix. If value x you are searching for is less than mid (center of the matrix) then move to upper-left matrix, if value x is greater than mid then move to lower-right matrix. Stop when you find the element x or element is not there.

binary search first col, then binary search row

One possible approach is to start from top right corner and apply modified binary search

public static int[] findElement(int[][] matrix , int key)
	{
		
		int[] result=new int[2];
		int col =matrix[0].length-1;
		
		int row =0;
		
		while(row< matrix.length && col >=0){
			
			if(matrix[row][col]==key){
				result[0]=row;
			    result[1]=col;
			    return result;
			}
			else if(matrix[row][col]>key){
				col--;
			}
			else {
				row++;
				
			}
				
		}
		
	
		return result;
	}

public static int[] findElement(int[][] matrix , int key)
	{
		
		int[] result=new int[2];
		int col =matrix[0].length-1;
		
		int row =0;
		
		while(row< matrix.length && col >=0){
			
			if(matrix[row][col]==key){
				result[0]=row;
			    result[1]=col;
			    return result;
			}
			else if(matrix[row][col]>key){
				col--;
			}
			else {
				row++;
				
			}
				
		}
		
	
		return result;
	}

I see many of you do binary search, go to middle.
I check the row and column that the number locates at by comparing the number with the maximum of each row and column. Also, at the beginning, i check if the number is within the value range of matrix. At the end, must check if number found or not. I use range here, so must have the last if statement.
The worst case and avg. case is O(rows + columns).


int Search(int[][] matrix, int num)
{
if( num > matrix[matrix.length][matrix[0].length] }} num < matrix[0][0])
return 0;
int columnIndex = 0;
for(int index = 0; index < matrix[0].length; index++)
{
if(num > matrix[matrix.length][index])
columnIndex++;
else
break;
}
int rowIndex = 0;
for(int index = 0; index < matrix.length; index++)
{
if(num > matrix[index][columnIndex])
rowIndex++;
else
break;
}

if(matrix[rowIndx][columnIndex] == num)
return matrix[rowIndex][columnIndex];

return 0;
}