74.搜索二维矩阵

题目描述

题解

二分查找

先对第一列进行二分查找, 确定出目标值在哪一行, 然后在该行进行查找.

public boolean searchMatrix(int[][] matrix, int target) {

    if (matrix.length < 1 || matrix[0].length<1 || matrix[0][0] > target || matrix[matrix.length - 1][matrix[0].length - 1] < target ) {
        return false;
    }

    int rowIndx = 0;

    int rleft = 0;
    int rright = matrix.length - 1;
    while (rleft <= rright) {
        int mid = rleft + (rright - rleft) / 2;
        if (matrix[mid][0] == target) {
            return true;
        } else if (matrix[mid][0] > target) {
            rright = mid - 1;
        } else {
            rleft = mid + 1;
        }
    }

    rowIndx = rright;

    rleft = 0;
    rright = matrix[0].length - 1;
    while (rleft <= rright) {
        int mid = rleft + (rright - rleft) / 2;
        if (matrix[rowIndx][mid] == target) {
            return true;
        } else if (matrix[rowIndx][mid] > target) {
            rright = mid - 1;
        } else {
            rleft = mid + 1;
        }
    }

    return false;
}