version at: 2022-04-07

/**
1. 因为从左到右顺序, 从上到下顺序, 所以从右上角开始找
2. 目标比它小就向左移动, 目标大就向右移动

*/

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        int i = 0;
        int j = matrix[0].length - 1;
        while (i < matrix.length && 0 <= j && matrix[i][j] != target) {
            if (matrix[i][j] < target) i++;
            else j--;
        }

        return i < matrix.length && 0 <= j && matrix[i][j] == target;
    }
}

/**
看成一个有序序列去二分搜索, 注意坐标转换
*/
class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        int n = matrix.length;
        int m = matrix[0].length;
        int i = 0;
        int j = n * m - 1;

        while (i < j) {
            int mid = (i + j) / 2;

            if (matrix[mid/m][mid%m] >= target) j = mid;
            else i = mid + 1;
        }

        return matrix[i/m][j%m] == target;
    }
}

// 1.单调-> 2分
// 2. bound
// 3. check
// 4. 特判
// 5. 转换是按列为分母？


class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) return false;

        int n = matrix.length, m =matrix[0].length;
        int l = 0 , r = n*m-1;
        while (l < r){
            int mid = (l+r)>> 1;
            int x = mid / m, y = mid % m;
            if(matrix[x][y] >= target) r= mid;
            else l = mid +1;
        }
        int x = l / m, y = l % m;
        return matrix[x][y] == target;
    }    

    public boolean searchMatrix2(int[][] matrix, int target) {
        if (matrix == null || matrix.length == 0) return false;
        int row = 0, col = matrix[0].length -1 ;
        while(  row < matrix.length && 0 <= col  ){
            int m = matrix[row][col];
            if (m == target) return true;
            else if (m < target) row ++;
            else col --;
        }
        return false;
    }
}