## Microsoft Interview Question

Software Engineer Interns**Team:**Bing

**Country:**United States

**Interview Type:**In-Person

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.

```
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;

}

The solution is here, rather, inverted.

- NoOne November 02, 2016geeksforgeeks.org/search-in-row-wise-and-column-wise-sorted-matrix/