I was looking for algorithm on searching a number in a 2D matrix, with property that the matrix is sorted both row-wise and column-wise. Finally i came across, this link http://www.programcreek.com/2013/01/leetcode-search-a-2d-matrix-java/. The only thing i couldn't understand was, on line number 13 and 14 where midX and midY are calculated as
int midX=mid/n
int midY=mid%n
where "n" is the number of colums
i am not unable to understand why for finding "midX" its divide by "n" and for finding "midY" its "mod(%)" by "n".
Can anyone pls help me understand the logic behind this?
Note first of all that X and Y do not hold their normal meaning in your expressions. X denotes the row and Y denotes the column.
It's leveraging that you could assign the elements of a matrix an index in a linear manner row-wise: \begin{array}{cccc} 0&1&2&3\\ 4&5&6&7\\ \end{array}
Given the width $W$, row $r$ and column $c$, the indices $i$ are related by:
\begin{align} i & = r \times W + c \\ r & = \lfloor i / W \rfloor \\ c & = i \pmod{W} \end{align}
There is an analogous mapping for number column-wise, but it's of no interest in this scenario.
As the problem of searching a sorted range of elements is well explored, the algorithm transforms the array into a linear sequence with the mapping above, searches the range, and transforms the resulting index back into the row/column index sought.
In particular, it's doing a binary search, which is the act of repeatedly halving an interval to find a value. It starts with the full range of elements, determines a midpoint index in that interval. It compares the element at that location and continues into the branch that ought to hold the value until either running out of elements or finding the element.