3 Java solutions: 2-binarySearch, 1-binarySearch-recursive and 1-binarySearch-iterative


  • 0
    E

    2-binarySearch

    public class Solution1 {
        // Two binary search: search target row, then search target value
        public boolean searchMatrix(int[][] matrix, int target) {
            if (matrix == null || matrix.length == 0 || matrix[0].length == 0) return false;
            int m = matrix.length, n = matrix[0].length;
            // target row
            int[] first = new int[m];
            for (int i = 0; i < m; i++) first[i] = matrix[i][0];
            int row = Arrays.binarySearch(first, target);
            if (row >= 0) return true;
            row = -(row + 1) - 1;
            // target value
            if (row < 0) return false;
            return Arrays.binarySearch(matrix[row], target) >= 0;
        }
    }
    

    1-binarySearch-recursive

    public class Solution2 {
        // One binary search: treat f[i] as matrix[i / n][i % n]
        // Recursive
        public boolean searchMatrix(int[][] matrix, int target) {
            if (matrix == null || matrix.length == 0 || matrix[0].length == 0) return false;
            int m = matrix.length, n = matrix[0].length;
            return binarySearch(matrix, n, target, 0, m * n - 1);
        }
    
        private boolean binarySearch(int[][] matrix, int n, int target, int lo, int hi){
            if (lo > hi) return false;
            int mid = lo + (hi - lo) / 2;
            int cmp = matrix[mid / n][mid % n] - target;
            if (cmp == 0) return true;
            else if (cmp > 0)
                return binarySearch(matrix, n, target, lo, mid - 1);
            else
                return binarySearch(matrix, n, target, mid + 1, hi);
        }
    }
    

    1-binarySearch-iterative

    public class Solution3 {
        // One binary search: treat f[i] as matrix[i / n][i % n]
        // Iterative
        public boolean searchMatrix(int[][] matrix, int target) {
            if (matrix == null || matrix.length == 0 || matrix[0].length == 0) return false;
            int m = matrix.length, n = matrix[0].length;
            int lo = 0, hi = m * n - 1;
            while (lo < hi){
                int mid = lo + (hi - lo) / 2;
                int cmp = matrix[mid / n][mid % n] - target;
                if (cmp == 0) return true;
                else if (cmp > 0) hi = mid - 1;
                else              lo = mid + 1;
            }
            return matrix[lo / n][lo % n] == target;
        }
    }
    

Log in to reply
 

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