题意
写出一个高效的算法来搜索 m × n矩阵中的值。
这个矩阵具有以下特性：
每行中的整数从左到右是排序的。
每行的第一个数大于上一行的最后一个整数。
性能要求，时间复杂度O（logm+logn）
解答
两次二分，第一次确定所在行，第二次确定所在列
代码
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 |
public boolean searchMatrix(int[][] matrix, int target) { // write your code here int m,n,mt = -1,nt = -1; if(matrix == null|| matrix.length == 0)return false; m = matrix.length; n = matrix[0].length; int h,l,mid; l = 0; h = m -1; while(l <= h&&h >= 0&&l < m){ mid = (l + h)/2; if(matrix[mid][0] > target){ h = mid - 1; }else if(matrix[mid][0] < target&&mid+1<m&&matrix[mid+1][0] < target){ l = mid + 1; }else{ mt = mid; break; } } if(mt < 0)return false; l = 0; h = n - 1; while(l <= h&&h >= 0&&l < n){ mid = (l + h)/2; if(matrix[mt][mid] > target){ h = mid - 1; }else if(matrix[mt][mid] < target){ l = mid + 1; }else{ nt = mid; break; } } if (nt < 0)return false; return true; } |
