Finding the element in the M X N matrix sorted in ascending order

Problem

Given an M $\times$ N matrix in which each row and each column are sorted in ascending order, write a method to find an element.

Binary search approach, $O( \log {N \times N})$

This is one of the binary search variations. If we split the matrix into M rows and stitch them together, we will have the one-dimensional array with N $\times$ M elements sorted in ascending order. (See Figure 1)

Now, we can perform the binary search within the range between 0 and $N \times M -1$. Once we get the position of the element in the middle, h We need to convert it into the coordinates within the matrix following formula:

  Column position  = h / N

  Row position = h % N

 Once the coordinates are calculated, we can compare them with the target value as we do in the binary search. The rest of the algorithm will be the same as the typical binary search.

Overall running time will be $$O(\log {N \times M})$$

Here is the complete code in C++.

Here is another solution in python

Practice statistics

19:30: to write up the solution

UPDATE(2022-06-13): Solved the problem again. The initial algorithm had the flaw in converting the linear position into the matrix position. Mistakenly used the number of rows when calculating the row position. Should've used the row length to get the correct value.