Java Complete Solution O(logm + logn)=O(logmn)


  • 0
    T
    public boolean searchMatrix(int[][] matrix, int target) {
    		if (matrix == null || matrix.length < 1 || matrix[0].length < 1)
    			return false;
    
    		int row = BSearchRec(matrix, target, 0, matrix.length - 1);
    		if (row == -1)
    			return false;
    		else
    			return BLinearSearchRec(matrix[row], target, 0, matrix[0].length - 1);
    	}
    
    	private int BSearchRec(int[][] mat, int target, int low, int high) {
    		if (low <= high) {
    			int mid = (low + high) / 2;
    			if (mat[mid][mat[0].length - 1] >= target) {
    				if (mid == 0 || mat[mid - 1][mat[0].length - 1] < target)
    					return mid;
    				else
    					return BSearchRec(mat, target, low, mid - 1);
    			} else
    				return BSearchRec(mat, target, mid + 1, high);
    		}
    		return -1;
    	}
    
    	private boolean BLinearSearchRec(int[] row, int target, int low, int high) {
    		if (low <= high) {
    			int mid = (low + high) / 2;
    			if (row[mid] == target)
    				return true;
    			else if (row[mid] >= target)
    				return BLinearSearchRec(row, target, low, mid - 1);
    			else
    				return BLinearSearchRec(row, target, mid + 1, high);
    		}
    		return false;
    	}
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.