74.md

74. 搜索二维矩阵

编写一个高效的算法来判断 m x n 矩阵中，是否存在一个目标值。该矩阵具有如下特性：

每行中的整数从左到右按升序排列。 每行的第一个整数大于前一行的最后一个整数。

示例 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

-104 <= matrix[i][j], target <= 104

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/search-a-2d-matrix 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

方法一

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
    	// 先确定target在哪一行，再遍历
        for (int[] row : matrix) {
            if (target <= row[row.length - 1]) {
                for (int col : row) {
                    if (col == target) {
                        return true;
                    }
                }
                break;
            }
        }
        return false;
    }
}

方法二

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        // 一次性二分查找（将每一行都拼接到上一行的末尾，会得到一个升序的一维数组，再进行二分查找）
        // 行
        final int m = matrix.length;
        // 列
        final int n = matrix[0].length;
        int low = 0;
        int high = m * n - 1;
        while (low <= high) {
            int mid = (high - low) / 2 + low;
            int curVal = matrix[mid / n][mid % n];
            if (curVal < target) {
                low = mid + 1;
            } else if (curVal > target) {
                high = mid - 1;
            } else {
                return true;
            }
        }
        return false;
    }
}