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