2.搜索二维数组

• 2.14
  • mid 值必须，定义 midVal 值需要都对 n 取商取余
  • 即：在矩阵的一维与二维坐标互相转换时，一切都跟 n（列数/行宽）有关，跟 m（行数）没有任何关系：

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        int m = matrix.length;
        int n = matrix[0].length;
 
        int row = 0;
        int col=0;
        int l = 0;
        int r = m*n-1;
        while(l<=r){
            int mid = (l+r)/2;
            int midVal = matrix[mid/n][mid%n];
            if(midVal==target) return true;
            if(midVal<target){
                l = mid+1;
            }else{
                r = mid-1;
            }
        }
        return false;
    }
}

• 1.31

  • 记住了定位，但是忘了 col 在前，row 在后，而且依旧`left⇐right·

• 1.20

  • 依旧没记住 midVal 定位问题 mid/n 与 mid%n，两个都是以 列 n 为取整取余的

• 11.17

  • 主要就是没记住二维数组的midVal定位问题int midVal = matrix[mid/n][mid%n];
  • right 为展平后数组的长度m*n-1
  • 其他到没什么问题

					[1,3,5,7]
					[10,11,16,20]
					[23,30,34,60]
					
					m=3，n=4
					
					mid = 7
					row = 7 / 4 = 1
					col = 7 % 4 = 3

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        int m = matrix.length;
        int n = matrix[0].length;
        int left = 0, right = m*n-1;
        while(left<=right){
            int mid = (left+right)/2;
            int midValue = matrix[mid/n][mid%n];
            if(midValue ==target) return true;
            else if(midValue<target) left = mid+1;
            else right = mid-1;
        }
        return false;
    }
}

• 就是把二维数组展开,需要注意一下

1. 我们可以把 (row, col) 映射到一个虚拟的一维下标 index = row * n + col；
2. 反过来：

• row = index / n
• col = index % n