JAVA using Binary Search, O(log mn = log m + log n) time complexity


  • -1
    Z
    public class Solution {
        public boolean searchMatrix(int[][] matrix, int target) {
            if(matrix == null || matrix.length == 0
    		 ||matrix[0] == null || matrix[0].length == 0){
    			return false;
    		}
    		return find(matrix,0,matrix[0].length-1,target);
        }
    	public boolean find(int[][] matrix, int row, int col,int target){
    		// when to return false?
    		if(matrix[row][col] == target){
    			return true;
    		}
    		
    		int midrow = 0, midcol = 0;
    		int up,down,left,right;
    		up = row; down = matrix.length-1;
    		while(up + 1 < down){
    			midrow = up + (down - up) / 2;
    			if(matrix[midrow][col] == target){
    				return true;
    			}
    			if(matrix[midrow][col] > target){
    				down = midrow;
    			}
    			else{
    				up = midrow;
    			}
    		}
    		if(matrix[up][col] == target || matrix[down][col] == target) return true;
    		if(matrix[up][col] > target){
    			midrow = up;
    		}
    		else if(matrix[down][col] > target){
    			midrow = down;
    		}
    		else return false;
    		
    		left = 0; right = col;
    		while(left + 1 < right){
    			midcol = left + (right - left) / 2;
    			if(matrix[midrow][midcol] == target){
    				return true;
    			}
    			if(matrix[midrow][midcol] < target){
    				left = midcol;
    			}
    			else{
    				right = midcol;
    			}
    		}
    		if(matrix[midrow][left] == target || matrix[midrow][right] == target) return true;
    		if(matrix[midrow][right] < target){
    			midcol = right;
    		}
    		else if(matrix[midrow][left] < target){
    			midcol = left;
    		}
    		else return false;
    		
    		
    		return find(matrix,midrow,midcol,target);
    		
    	}
    }
    

Log in to reply
 

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