题目

74. 搜索二维矩阵

题解

按照行进行遍历，对每一行中的数据进行二分查找即可。

代码

public class code74 {

    public static 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;

        for (int i = 0; i < m; i++) {
            if (matrix[i][0] <= target && target <= matrix[i][n - 1]) {
                int left = 0;
                int right = n - 1;
                while (left <= right) {
                    int mid = left + (right - left) / 2;
                    if (matrix[i][mid] == target) {
                        return true;
                    } else if (matrix[i][mid] > target) {
                        right = mid - 1;
                    } else if (matrix[i][mid] < target) {
                        left = mid + 1;
                    }
                }
            }
        }
        return false;
    }

    // public static 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;

    // for (int i = 0; i < m; i++) {
    // for (int j = 0; j < n; j++) {
    // if (matrix[i][j] == target) {
    // return true;
    // }
    // }
    // }
    // return false;
    // }

    public static void main(String[] args) {
        // int matrix[][] = {};

        // int matrix[][] = { {}, {}, {} };

        int matrix[][] = { { 1, 3, 5, 7 }, { 10, 11, 16, 20 }, { 23, 30, 34, 50 } };

        int target_1 = 3;
        boolean flag_1 = searchMatrix(matrix, target_1);
        System.out.println(flag_1);

        int target_2 = 13;
        boolean flag_2 = searchMatrix(matrix, target_2);
        System.out.println(flag_2);
    }
}

参考

  1. 搜索二维矩阵——题解一
  2. O(log(mn)) = O(log(m) + log(n))——题解二
  3. 按照行进行遍历
  4. 【特别推荐】十分好用的二分查找法模板（Python 代码、Java 代码）
  5. java实现二分查找-两种方式
  6. 二分查找、二分边界查找算法的模板代码总结
  7. java中获取二维数组的行数和列数