本文共 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/