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.
Consider the following matrix:
[ [1, 3, 5, 7], [10, 11, 16, 20], [23, 30, 34, 50] ]Given target = 3, return true.
本题实际是对矩阵进行一次查找，如果进行逐个遍历，时间复杂度会是O( n2 )。根据矩阵的性质，我们可把这个矩阵看作一个正序数组，那么对有序数组进行遍历查找效率较高的方法还是折半查找法（或叫二分查找法）。折半查找意味着每次取查找范围中间的数，即等于查找范围长度一半的序号的数，将其与给定目标数进行比较，在不相等的情况下，如果大于则查找范围变为所取的数的后半部分，如果小于则查找范围为所取的是的前半部分，这样搜索范围收缩为原来的一半，通过这样递归，最后循环结果在查询范围等于0，也就是落在一个数上，这种方法查询效率（时间复杂度）可为O( logn )。值得一提的是，对于元素个数为奇偶数的数组，其中间的序号可通过折半向下取整得到。
在本题，由于操作的是二维矩阵，我们需要得到二维矩阵中间的数。一维数组和二维矩阵 m×n 序号对应的关系是 array[i] = array[i/n][i%n]，因此可以根据这个可以找到中间数。下面是使用C++的实现方法。
class Solution{ public: bool searchMatrix(vector<vector<int> >& matrix, int target) { int row = matrix.size(); int column = matrix[0].size(); int left = 0; int right = row*column-1; while (left != right){ int mid = (l + r - 1) >> 1;//相当于做除以2运算，使用右移运算符效率更高 if (matrix[mid/column][mid%column] < target) left = mid + 1; else right = mid; } return (matrix[right/column][right%column] == target); } } };