Binary Search on Matrix

Problem Statement — check whether an element is present in a matrix of size n*m in which rows & columns are sorted in increasing order.

Sample Input -

[ [1, 3, 12],

[2, 4 , 20],

[5, 10, 30]]

k=4

Output

true

Solution :

The initial thought is to apply binary search on each row & if any of the rows have an element then return true else return false.

The time complexity of the solution is O(n log m) which is better than brute-force solution when you iterate over all elements which result to O(n*m)

This can be solved in a better way using binary search.

Note- rows & columns are placed in sorted order so element present on left cell of the current element will be smaller than current value & element present below the current element will be greater than current value.

let’s consider element 4 in the above sample input, an element present on the left side of 4 will be smaller (2<4) & element present below element 4 will be greater than 4(4<10)

so if we start from the top right corner element of the matrix then we can compare the target element will the current element & move accordingly as per comparison.

let's say in the above example-

Top right corner element is 12 & target element is 4

if the current element is lesser than the target element then move in the cell below it because we know the below element will greater than the current element else move in left cell of the current element so we, in this case, will move left cell of element 12 which is element 3 & if we compare again with target element 4 then we will move below since current elemet is lesser than target hence we found target element 4

since the size of the matrix is n*m so from the top right corner we can move n cells below & m cells left side from the top left corner.

Hence time complexity is O(n+m)

CODE —

public boolean brinarySearch(int grid[][], int k){

int n = grid.length;

int m = grid[0].length;

if(k < grid[0][0] || k> grid[n-1][m-1])

return false;

int i=0, j=m-1; \\ top right corner position

while(j≥0 && i<n){

if(grid[i][j] == k)

return true;

else if (grid[i][j] > k)

j-- ;

else

i++;

}

return false;

}