本文共 2438 字，大约阅读时间需要 8 分钟。

解法一：看成一个sorted一维数组

public class Solution {    public boolean searchMatrix(int[][] matrix, int target) {        if (matrix == null || matrix.length == 0) {            return false;        }        int row = matrix.length;        int col = matrix[0].length;        int beg = 0;        int end = row * col - 1;        while (beg < end) {            int mid = beg + (end - beg) / 2;            int tmp = matrix[mid / col][mid % col];            if (tmp == target) {                return true;            } else if (tmp > target) {                end = mid;            } else {                beg = mid + 1;            }        }        return matrix[end / col][end % col] == target;    }}

解法二：从右上角二分，这样code比较复杂，但是局部访问原理不好，可能一直访问列

public class Solution {    public boolean searchMatrix(int[][] matrix, int target) {        if (matrix == null || matrix.length == 0) {            return false;        }        int row = 0;        int col = matrix[0].length - 1;        while (row < matrix.length && col >= 0) {            if (matrix[row][col] == target) {                return true;            } else if (matrix[row][col] > target) {                int index = hSearch(matrix, row, target);                if (index < matrix[0].length && matrix[row][index] == target) {                    return true;                }                if (col == index) {                    return false;                }                col = index;            } else {                int index = vSearch(matrix, col, row, target);                if (index < matrix.length && matrix[index][col] == target) {                    return true;                }                if (row == index) {                    return false;                }                row = index;            }        }        return false;    }    private int hSearch(int[][] matrix, int pos, int target) {        int index = Arrays.binarySearch(matrix[pos], target);        return index >= 0 ? index : -(index + 1);    }    private int vSearch(int[][] matrix, int pos, int beg, int target) {        int end = matrix.length - 1;        while (beg < end) {            int mid = beg + (end - beg) / 2;            if (matrix[mid][pos] == target) {                return mid;            } else if (matrix[mid][pos] > target) {                end = mid - 1;            } else {                beg = mid + 1;            }        }        return matrix[beg][pos] >= target ? beg : beg + 1;    }}

转载地址：http://uvhld.baihongyu.com/