LeetCode-74-搜索二维矩阵

题目

讲解

由于整个二维数组是有序的，根据题干可以得知，每一行是有序的，每一列是有序的，所以我们可以通过两次二分查找得到结果；

• 还是不变的y总二分模板

第一次二分用来查找是第几行，第二次用来查找是第几列；

题解

下边的题解展示了两种二分写法，注意第一次二分一定得是找小于等于target的值，不然会出现
[[1,2,3],[4,5,6],[7,8,9]]
如果target是3
这个二维数组第一次二分找的是大于等于3的行，会找到第二行

第二次二分就没什么需要判断的了，找小于等于或大于等于的都可以，
因为最后return时，还会进行一次判断

public boolean searchMatrix(int[][] matrix, int target) {
        int temp_row = 0;
        int temp_col = 0;

        int row_l = 0;
        int row_r = matrix.length-1;

        while(row_l < row_r){
            int row_mid = (row_l+row_r+1)/2;
            //找到第一个小于或等于target的值
            if(matrix[row_mid][0] <= target){
                row_l = row_mid;
            }else{
                row_r = row_mid-1;
            }
        }
        temp_row = row_l;

        int col_l = 0;
        int col_r = matrix[0].length-1;

        while(col_l < col_r){
            int clo_mid = (col_l+col_r)/2;
			//找到第一个大于或等于target的值
            if(matrix[temp_row][clo_mid] >= target){
                col_r = clo_mid;
            }else{
                col_l = clo_mid + 1;
            }
        }
        temp_col = col_l;

        if(matrix[temp_row][temp_col] == target){
            return true;
        }else{
            return false;
        }
    }