Lintcode28 Search a 2D Matrix solution solution

[topic description]

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.

Write an efficient algorithm to search for values in m × n matrix.

This matrix has the following characteristics: integers in each row are sorted from left to right. The first number of each row is greater than the last integer of the previous row.

[topic link]

Http://www.lintcode.com/en/problem/search-a-2d-matrix/

[topic Analysis]

For this given matrix, if we use the brute force solution and two nested loops, O (N2) can get the answer. But what we need to note is that this question has given two properties of the matrix.

It is very helpful to increase the time complexity of our algorithm. first of all, we give a solution of O (n), that is, we can fix the elements in the upper right corner, and according to the law of increasing or decreasing, we can judge whether the given value exists in this matrix.

[reference answer]

Http://www.jiuzhang.com/solutions/search-a-2d-matrix/