题解 | #矩阵查找#（附带图解）

思路:

从题中给出的有效信息有两点：

• 每一行的数字都从左到右递增
• 每一行的第一个数字都比上一行最后一个数字大

故此此矩阵是有序的，可以使用传统的二分查找进行取值。

方法一：两次二分查找

具体做法：
我们可以先通过二分查找确定 行，再对该 行 继续进行二分查找 ，思维较为常见，不做过多解读

import java.util.*;
public class Solution {
    /**
     * 
     * @param matrix int整型二维数组 
     * @param target int整型 
     * @return bool布尔型
     */
    public boolean searchMatrix (int[][] matrix, int target) {
        // write code here
        int N = matrix.length, M = matrix[0].length, left = 0, right = N - 1;
        while (left <= right) {
            int center = (right - left) / 2 + left;
            //比较每行的第一个元素
            if (matrix[center][0] == target) return true;  
            else if (matrix[center][0] < target) { 
                //center行的最后一个元素
                if (matrix[center][M - 1] == target) return true;  
                else if (matrix[center][M - 1] < target) left = center + 1;
                else if (matrix[center][M - 1] > target) { 
                    if (confirm(matrix[center], target)) return true;
                    else return false;
                }
            } else if (matrix[center][0] > target) {
                right = center - 1;
            }
        }
        return false;
    }
    private boolean confirm(int[] matrix, int target) {
        int N = matrix.length, left = 0, right = N - 1;
        while (left <= right) {
          int center = (right - left) / 2 + left;
          if (matrix[center] == target) return true;
          else if (matrix[center] < target) left = center + 1;
          else right = center - 1;
        }
        return false;
    }
}

复杂度分析：

• 时间复杂度：O(logmn)，其中 m是矩阵的行 和 n 是矩阵的列
• 空间复杂度：O(1)，原有数组上进行操作，未申请额外空间

方法二：一次二分查找

具体做法：
因为 每一行的第一个数字都比上一行最后一个数字大 ，所以我们可以通过 数学的方法 将其压缩为一个 一维矩阵 ，具体思路如下图所示

import java.util.*;
public class Solution {
    /**
     * 
     * @param matrix int整型二维数组 
     * @param target int整型 
     * @return bool布尔型
     */
    public boolean searchMatrix (int[][] matrix, int target) {
        // write code here
        int M = matrix.length, N = matrix[0].length,left = 0, right = M * N - 1;
        while (left <= right) {
            int center = ( right - left) / 2 + left;
            int compute = matrix[center / N][center % N];
            if (compute < target) {
                left = center + 1;
            } else if (compute > target) {
                right = center - 1;
            } else {
                return true;
            }
        }
        return false;
    }
}

复杂度分析：

• 时间复杂度：O(logmn)，其中 m是矩阵的行 和 n 是矩阵的列
• 空间复杂度：O(1)，原有数组上进行操作，未申请额外空间