[数据结构与算法]java：（搜索二维矩阵）编写一个算法来判断m*n矩阵中，是否存在一个目标值

74.搜索二维矩阵

思路：
若将矩阵每一行拼接在上一行的末尾，则会得到一个升序数组，我们可以在该数组上二分找到目标元素。代码实现时，可以二分升序数组的下标，将其映射到原矩阵的行和列上。

答案：

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        //记录二维数组的行和列
        int m = matrix.length;
        int n = matrix[0].length;
        //二维数组每一个元素都比前一个元素大，所以可以想象成一个升序的一维数组
        //记录一维数组的起始下标和末尾下标
        int low = 0;
        int high = m*n-1;
        //二分法
        while(low <= high){
            //获取中间值的下标
            int mid = (high + low) / 2 ;
            //获取中间值
            int midNum = matrix[mid/n][mid%n];
            
            if(target > midNum){ //如果目标值大于中间值
                low = mid+1; //就从一维数组中下标值在mid之后的一段中找
            }else if(target < midNum){
                high = mid-1; //在前半部分找
            }else{ //target == midNum; 从数组中找到了目标值
                return true;
            }
        }
        return false;
    }
}

接下来看下这题的另一个变式

240. 搜索二维矩阵 II

思路：
这题和上一题不一样的点在于矩阵的规律是不一样的，这题矩阵中，每一行是升序的，每一列也是升序的，但不能保证每一行的第一个元素大于上一行的最后一个元素。既然每一行的第一个元素是这一行中最小的，且比上一行的第一个元素大，那么就可以以行中第一个元素的值作为判断点，如果目标值小于当前行的首元素，那么目标值绝对不可能在当前值的后面，只能前面几行，然后在将target与上一行的首元素比较，如果还是target更下，那么继续上一行，以此类推；如果说在某一行比较的时候，target大于该行的首元素，那就然后target和当前行中其他列的元素匹配。

答案：

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        //用row表示数组最后一行的下标
         int row = matrix.length-1;
         //用col表示列的下标
         int col = 0;
         //
         while(row>=0 && col<matrix[0].length){
             //如果目标值小于当前行的第一个元素，就继续从上一行找
             if(target < matrix[row][col]){
                 row--;
             }else if(target > matrix[row][col]){
                 //如果目标值大于当前行的第一个元素，就从下一列开始匹配
                 col++;
             }else{
                 return true;
             }
         }
         return false;
    }
}