LeetCode 搜索二维矩阵 / search a 2D matrix

题目描述：

    解题思路：题目要求尽可能快，自然想到双重二分，难点是边界判断要搞清楚，建议写之前大脑先模拟一下，头尾两个指针（start 和 end） 越考越近的时候会发生什么。

这时候会出现两种情况 （1）：start 和 end 重合，然后在循环判断一次结束

                               （2）：start 和 end 相邻，然后在循环判断一次，这时候可能直接结束也有可能转换成情况（1）

模拟一下你就会发现无论是以哪种情况结束，答案都会在 matrix[mid] 或 matrix[mid - 1] 这两行中产生，所以第二次二分时直接对这两行判断即可。代码如下：

class Solution {
	public:
		bool searchMatrix(vector<vector<int>>& matrix, int target) {
			int m = matrix.size();
            if(m == 0) return false;
			int n = matrix[0].size();
            if(n == 0) return false;
			int start = 0,end = m - 1;
			int start0,end0,mid,mid0;
			while(start <= end){    //第一次二分
				mid = (start + end) / 2;
				if(matrix[mid][0] > target){
					end = mid - 1;
				}
				else if(matrix[mid][0] < target){
					start = mid + 1;
				}
				else{
					return true;
				}
			}
			if(matrix[mid][0] < target){  //第二次二分
			//答案可能出现在 matrix[mid] 或 matrix[mid - 1]这两行中的其中一行
				n = matrix[mid].size();
				start0 = 0;
				end0 = n - 1;
				while(start0 <= end0){
					mid0 = (start0 + end0) / 2;
					if(matrix[mid][mid0] > target){
						end0 = mid0 - 1;
					}
					else if(matrix[mid][mid0] < target){
						start0 = mid0 + 1;
					}
					else{
						return true;
					}
				}
			}
			else if(mid - 1 >= 0 && matrix[mid - 1][0] < target){ //答案可能出现在 matrix[mid] 或 matrix[mid - 1]这两行
				n = matrix[mid - 1].size();
				start0 = 0;
				end0 = n - 1;
				while(start0 <= end0){
					mid0 = (start0 + end0) / 2;
					if(matrix[mid - 1][mid0] > target){
						end0 = mid0 - 1;
					}
					else if(matrix[mid - 1][mid0] < target){
						start0 = mid0 + 1;
					}
					else{
						return true;
					}
				}
			}
			return false;
		}
	};