74. 搜索二维矩阵(中等)

1，问题描述

74. 搜索二维矩阵

难度：中等

给你一个满足下述两条属性的 m x n 整数矩阵：

• 每行中的整数从左到右按非严格递增顺序排列。
• 每行的第一个整数大于前一行的最后一个整数。

给你一个整数 target ，如果 target 在矩阵中，返回 true ；否则，返回 false 。

示例 1：

输入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3
输出：true

示例 2：

输入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 13
输出：false

提示：

• m == matrix.length
• n == matrix[i].length
• 1 <= m, n <= 100
• -10^4 <= matrix[i][j], target <= 10^4

2，思考过程

​ 模式识别：有序、查找某个值，直接就想到了二分查找法

​ 解法1:先确定在哪一行，在确定在哪一列

​ 解法2:直接整理成一维有序数组的概念，进行二分查找

3，代码处理

import java.util.Arrays;

public class _74搜索二维矩阵 {

    // 解法：1次二分查找,整理成一维数组，再二分查找
    public boolean searchMatrix_binary(int[][] matrix, int target) {
        int rowsLen = matrix.length, colsLen = matrix[0].length;
        int len = rowsLen * colsLen;
        int left = 0, right = len;
        while (left < right) {
            int mid = (left + right) / 2;
            int x = mid / colsLen;
            int y = mid % colsLen;
            if (matrix[x][y] == target) return true;
            if (matrix[x][y] < target) left = mid + 1;
            else right = mid;
        }
        return false;
    }

    // 解法：两次，二分查找列
    public boolean searchMatrix_twice_binary(int[][] matrix, int target) {
        // 二分查找列
        int rowsLen = matrix.length, colsLen = matrix[0].length;
        int[] colsNum = new int[rowsLen];
        for (int i = 0; i < rowsLen; i++) colsNum[i] = matrix[i][colsLen - 1];
        int rowIdx = Arrays.binarySearch(colsNum, target);
        if (rowIdx < 0) rowIdx = -(rowIdx + 1);
        int colIdx = Arrays.binarySearch(matrix[rowIdx], target);
        return colIdx >= 0;
    }

    public static void main(String[] args) {
        _74搜索二维矩阵 searchMatrix = new _74搜索二维矩阵();
        System.out.println(searchMatrix.searchMatrix_binary(new int[][]{{1, 3, 5, 7}, {10, 11, 16, 20}, {23, 30, 34, 60}}, 15));
        System.out.println(searchMatrix.searchMatrix_twice_binary(new int[][]{{1, 3, 5, 7}, {10, 11, 16, 20}, {23, 30, 34, 60}}, 15));
    }
}