刷题笔记

74. Search a 2D Matrix

题目

Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties:

Integers in each row are sorted from left to right.
The first integer of each row is greater than the last integer of the previous row.

思路

1. 这是一道经典binary search，只不过是将一个数列化为矩阵。
2. 那么反其道而行之，只需要把mid的数值转化成矩阵的横纵坐标就可以进行比较了。

代码实现

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        int m = matrix.length, n = matrix[0].length;
        int left = 0, right = m * n - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            int i = mid / n, j = mid % n;
            if (matrix[i][j] == target) return true;
            else if (matrix[i][j] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return false;
    }
}

注意一个易错点，right = m * n - 1。因为left是从0开始的。