[LeetCode]Search a 2D Matrix II

和I不同，这道题无法转变为1D的sorted array，也无法先搜索列确定target在哪一行。但是题目给定matrix的性质，从左到右从上到下sort意味着我们可以找到某些性质进行二分。假设我们总右顶点开始，假设当前右顶点数是curr：

• if curr < target，那么所在的那一行就可以排除，因为那一行所有的数全部小于等于curr，target不可能在其中
• 相同的，if curr > target，那么curr所在的那一列就可以排除
• if curr == target, return true

时间复杂度O(m + n)，我们每一次排除一行或者一列。代码如下：

	class Solution {
	public:
	bool searchMatrix(vector<vector<int>>& matrix, int target) {
	int m = matrix.size(), n = m? matrix[0].size(): 0, i = 0, j = n - 1;
	while(i < m && j >= 0)
	{
	int curr = matrix[i][j];
	if(curr < target)++i;
	else if(curr > target)--j;
	else return true;
	}
	return false;
	}
	};

view raw Search a 2D Matrix II.cpp hosted with ❤ by GitHub