编写一个高效的算法，在 m x n 矩阵中搜索一个值。 该矩阵具有以下性质：

1. 每行中的整数从左到右排序。 2) 每行的第一个整数大于前一行的最后一个整数。

例如，考虑以下矩阵：

[
  [1,   3,  5,  7],
  [10, 11, 16, 20],
  [23, 30, 34, 50]
]

给定目标 = 3，返回 true。

Java 解决方案

这是一个典型的二分查找问题。

您可以尝试通过先查找行然后查找列来解决此问题。 没有必要这样做。 由于矩阵的特殊性，矩阵可以被认为是一个排序数组。 目标是使用二分搜索在这个排序数组中找到元素。

public class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        if(matrix==null || matrix.length==0 || matrix[0].length==0) 
            return false;
 
        int m = matrix.length;
        int n = matrix[0].length;
 
        int start = 0;
        int end = m*n-1;
 
        while(start<=end){
            int mid=(start+end)/2;
            int midX=mid/n;
            int midY=mid%n;
 
            if(matrix[midX][midY]==target) 
                return true;
 
            if(matrix[midX][midY]<target){
                start=mid+1;
            }else{
                end=mid-1;
            }
        }
 
        return false;
    }
}