搜索二维矩阵 II

思路

其实总的思想就是二分查找，但是其中的一个技巧是当查找不到的时候返回 right 值，这时间的 right 值指向值的特性是 a[right] < target其次需要注意的是一定要处理好 边界条件 和特殊的 测试值

代码

public static int searchMatrix(int[][] matrix, int target) { if (matrix.length == 0) { //处理特殊的测试值 return 0; } int count = 0; int col = matrix[0].length; //列 int row = matrix.length; //行 int[] T = new int[row]; for (int i = 0; i < row; i++) { T[i] = matrix[i][0]; } int result = find(T, target); if (result < 0) { //处理特殊的测试值，当matrix[0][0] > target ,此时返回的是负值 return 0; } if (matrix[result][0] == target) { count++; result--; } if (result < 0) { return count; } for (int i = 0; i <= result; i++) { if (matrix[i][col-1] >= target) { // 注意这里一定要测试最后一个值和target的关系 int temp = find(matrix[i], target); if (matrix[i][temp] == target) { count++; } } } return count; } public static int find(int[]a, int target) { int left = 0; int right = a.length - 1; int mid = 0; while(left <= right) { mid = (left + right) / 2; if (a[mid] == target) { return mid; }else if (a[mid] < target) { left = mid + 1; }else { right = mid - 1; } } return right; }

代码