Search a 2D Matrix ||(O(m + n) approach)

a naive approach:

Time complexity should be m * log(n).

How to achieve O(m + n) time complexity:

从右上角或者左下角开始search。从左下开始，当matrix[i][j]的值小于target时，排除所在行，因为右边的总比其大不需要比较，i--；

当matrix[i][j]的值大于target时，排除所在列，因为上边的总比其小不需要比较，j++; 当matrix[i][j]的值等于target时，排除所在行，列，i--，j++；

O(n ^ 1.58)解法：

参考：https://leetcode.com/discuss/47528/c-with-o-m-n-complexity

分治法，以矩形中点为基准，将矩阵拆分成左上，左下，右上，右下四个区域

若中点值 < 目标值，则舍弃左上区域，从其余三个区域再行查找

若中点值 > 目标值，则舍弃右下区域，从其余三个区域再行查找

时间复杂度递推式：T(n) = 3T(n/2) + c

n为row length

相关博文：http://articles.leetcode.com/2010/10/searching-2d-sorted-matrix-part-ii.html