Row search then col search (using Java 8 Function)


  • 0
    public class Solution {
        
        public boolean searchMatrix(int[][] matrix, int target) {
            if (matrix == null || matrix.length == 0 || matrix[0].length == 0) return false;
            
            Function<Integer, Integer> getRowValue = (row) -> matrix[row][0];
            int possibleRow = binarySearch(getRowValue, matrix.length - 1, target);
            
            if (possibleRow >= 0) return true; // we already found the item in the first column, return true
            if (possibleRow == -1) return false; // item is smaller then entire matrix[0][0], return false
            
            int row = -(possibleRow + 2); // + 1 would get us the successor, + 2 get's us the predecessor 
            Function<Integer, Integer> getColValue = (col) -> matrix[row][col];
            
            return binarySearch(getColValue, matrix[0].length - 1, target) >= 0;
        }
        
        private int binarySearch(Function<Integer, Integer> getValue, int hi, int val) {
            int lo = 0;
            while (lo <= hi) {
                int mid = (lo + hi) >>> 1;
                
                int midVal = getValue.apply(mid);
                
                if (midVal < val)
                    lo = mid + 1;
                else if (midVal > val)
                    hi = mid - 1;
                else
                    return mid; // val found
                    
            }
            return -(lo + 1); // val not found
        }
    }
    

Log in to reply
 

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