Sunday, June 15, 2014

Search a 2D Matrix (Java + Python)

Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties:

  • Integers in each row are sorted from left to right.
  • The first integer of each row is greater than the last integer of the previous row.

For example,

Consider the following matrix:

[
[1, 3, 5, 7],
[10, 11, 16, 20],
[23, 30, 34, 50]
]

For an  O (rows * cols) solution is too simple to meet the interviewer’s expectation. So what is the better solution should be? Binary search should be a good tool when I face search problem, however, how BS could be apply  in matrix?   if we regard 0 as start point, total_cols*total_rows-1 as the end point to look the matrix as a array then we can apply BS. However, how could we convert the position to row_NO and col_NO?  We  know row_NO * total_cols+col_NO=position, So in programming  row_NO=postion/total_cols, col_NO=postion%total_cols. then we can adapt this feature in our program  to apply binary search to get O(log(cols+rows)) search