74. Search a 2D Matrix

matrix = [
  [1,   3,  5,  7],
  [10, 11, 16, 20],
  [23, 30, 34, 50]
]
target = 3

对每一行进行一次二分法

public boolean searchMatrix(int[][] matrix, int target) {
    for (int i = 0; i < matrix.length; i++) {
        int l = 0, r = matrix[i].length;
        while (l < r) {
            int mid = (l + r) >>> 1;
            if (target == matrix[i][mid]) {
                return true;
            } else if (matrix[i][mid] < target){
                l = mid + 1;
            } else {
                r = mid;
            }
        }
    }
    return false;
}

因为并成一整行之后的数字刚好也是有序的，所以可以把整个矩阵看成一行进行排列

public boolean searchMatrix(int[][] matrix, int target) {
    if (matrix.length == 0 || matrix[0].length == 0) return false;
    int row = matrix.length, col = matrix[0].length;
    int l = 0, r = row * col;
    while (l < r) {
        int mid = (l + r) >> 1;
        int mid_value = matrix[mid / col][mid % col];
        if (mid_value == target) {
            return true;
        }
        if (mid_value < target) {
            l = mid + 1;

        } else {
            r = mid;
        }
    }
    return false;
}

mid_value的坐标计算：row=mid/col, col=mid%col

mid: 6 mid_value: 16
mid: 3 mid_value: 7
mid: 1 mid_value: 3