LeetCode 74. 搜索二维矩阵（二分查找）

示例 1:
输入:
matrix = [
  [1,   3,  5,  7],
  [10, 11, 16, 20],
  [23, 30, 34, 50]
]
target = 3
输出: true

class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        if(matrix.size()==0 || matrix[0].size() == 0)
            return false;
        //在第一列搜索最后一个比我小的
        int i, r = matrix.size(), c = matrix[0].size();
        int left = 0, right = r-1, mid;
        while(left <= right)
        {
        	mid = left + ((right-left)>>1);
        	if(matrix[mid][0] == target)
        		return true;
        	if(matrix[mid][0] < target)
        	{
        		if(mid == r-1 || matrix[mid+1][0] > target)
        			break;//mid行搜索即可
        		else
        			left = mid+1;
        	}
        	else
        		right = mid-1;
        }
        int R = mid;
        left = 0, right = c-1;
        while(left <= right)
        {
        	mid = left + ((right-left)>>1);
        	if(matrix[R][mid] == target)
        		return true;
        	if(matrix[R][mid] < target)     
        		left = mid+1;
        	else
        		right = mid-1;
        }
    	return false;
    }
};

class Solution {
	public:
	bool searchMatrix(vector<vector<int>>& matrix, int target) {
		if(matrix.size()==0 || matrix[0].size() == 0)
	            return false;
	    int i, r = matrix.size(), c = matrix[0].size();

		// 二分查找
		int left = 0, right = r * c - 1;//关键点
		int mid, val;
		while (left <= right) 
		{
			mid = (left + right) / 2;
			val = matrix[mid/c][mid%c];//关键地方
			if (target == val) 
				return true;
			else 
			{
				if (target < val) 
					right = mid - 1;
				else 
					left = mid + 1;
			}
		}
		return false;
	}
};