### Search smallest number in a binary matrix binary searching matrix    Posted: 5 years ago Updated: 4 years ago Edit answers (1) views (2421)

Suppose you are given an $$N \times N$$ binary matrix with following properties -

Each row is sorted ( 0 's followed by 1 's)
Each row is unique (No duplicates)
Each row represents an unsigned integer

How will you find the row representing the smallest integer.

 Posted: 5 years ago 0 0 Edit Since the binary matrix has dimension $$N \times N$$ and the digits in each row are sorted in ascending order, there will be atmost N+1 unique values. e.g , for N=3 , matrix can be formed from any 3 of the $$\left( \begin{array}{lll}0 & 0 & 0 \\0 & 0 & 1 \\0 & 1 & 1 \\1 & 1 & 1\end{array} \right)$$ rows.Similarly for N=4 and N=5 , matrix rows can be from any 4 and 5 of the $$\left( \begin{array}{llll}0 & 0 & 0 & 0\\0 & 0 & 0 & 1 \\0 & 0 & 1 & 1 \\0 & 1 & 1 & 1 \\1 & 1 & 1 & 1\end{array} \right)$$ and $$\left( \begin{array}{lllll}0 & 0 & 0 & 0 & 0\\0 & 0 & 0 & 0 & 1 \\0 & 0 & 0 & 1 & 1 \\0 & 0 & 1 & 1 & 1\\0 & 1 & 1 & 1 & 1\\1 & 1 & 1 & 1 & 1\end{array} \right)$$ rows respectively.The algorithm works as : Start from the first element at array[0][0] . If it is 0 , check the element right to it at array[0][1] . If it is 1 , skip this row and check the element in the next row but same column. Repeat the last two steps until all the rows have been visited or find a row with all zeros. Time complexity = $$O(N)$$.public int findSmallestEleminBinaryMatrix(int[][] array){ int i = 0; int j = 0; int rowNumber = 0; /* Iterate through the rows from first to last */ while(i < array.length){ /* At each row check whether the element is '0' or '1' */ /* Check until the element is '0' */ while(j < array.length & & array[i][j] == 0) { j++; if(rowNumber != i) rowNumber = i; /* End of row : Visited all the columns in this row */ if(j == array.length) break; } i++; } return rowNumber; }