Simple Java Solution O(logN)


  • 0
        public static boolean searchMatrix(int[][] matrix, int target) {
    		int start = 0;
    		int end = matrix.length*matrix[0].length-1;
    		while(start<=end) {
    			int middle = matrix[((start+end)/2)/matrix[0].length][((start+end)/2)%matrix[0].length];
    			if(middle==target) return true;
    			else if(middle<target) start=((start+end)/2)+1;
    			else end=((start+end)/2)-1;
    		}
    		return false;
    	}
    

    we can consider the matrix as a normal sorted array and apply binary search:

    1. the row index of the middle element will be
      ((start+end)/2)/matrix[0].length
    2. the column index of the middle element will be
      ((start+end)/2)%matrix[0].length
    3. if middle element < target increase start by one and recompute
      middle element
    4. if middle element > target decrease end by one and recompute middle
      element

Log in to reply
 

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