class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        int r = binarySearch(matrix,target);
        if(r ==-1)
            return false;
        boolean isfound = findbinary(matrix ,r, target);
        return isfound;
    }
    public static boolean findbinary(int[][] matrix , int r , int target){
        int l =0;
        int h = matrix[0].length-1;
        
        while(l<=h){
            int mid = l+(h-l)/2;
            if(matrix[r][mid]== target)
                return true;
            else if(matrix[r][mid]<target)
                l = mid+1;
            else
                h = mid-1;
        }
        return false;
    }
    
    
    public static int binarySearch(int[][] matrix , int target){
        int l =0;
        int h = matrix.length-1;
        int lc = matrix[0].length-1;
        while(l<=h){
            int mid = l+(h-l)/2;
            if(matrix[mid][0] <= target && matrix[mid][lc] >= target){
                return mid;
            }
            else if(matrix[mid][0] > target){
                h = mid-1;
            }
            else{
                l = mid +1;
            }
        }
        return -1;
    }
}