Making use of Arrays.binarySearch in Java, 1ms.


  • 0
    A
    public class Solution {
        public boolean searchMatrix(int[][] matrix, int target) {
            int h = matrix.length;
            if(h == 0) return false;
            int w = matrix[0].length;
            
            int [] colZero = new int[h];
            for(int i=0;i<h;i++) colZero[i] = matrix[i][0];
            
            int row = Arrays.binarySearch(colZero,target);
            if(row >= 0) return true; // target is at the leftmost column
            
            int insertPoint = -row-1; // row = -(insertion point) - 1  i.e see http://bit.ly/29E7wzs
            int targetRow   = insertPoint-1;           // we want to find at the row before insertion point
            if(targetRow >= h || targetRow < 0) return false; // target outside matrix
            
            int col = Arrays.binarySearch(matrix[targetRow],target);
            return col >= 0; // otherwise not in this row.
        }
    }
    

Log in to reply
 

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