My O(lgm + lgn) java solution using binary search


  • -1
    G
    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 search(matrix, target, 0, matrix.length - 1, 0, matrix[0].length - 1);
        }
        
        private boolean search(int[][] matrix, int target, int up, int down, int left, int right) {
            int upOld = up, downOld = down, leftOld = left, rightOld = right;
            // System.out.println("up"+up+"down"+down+"left"+left+"right"+right);
            if (up == down && left == right){
                if (matrix[up][left] == target) return true;
                else return false;
            }
            while (left < right - 1 || up < down - 1) {
                int midH = left + (right - left) / 2;
                int midV = up + (down - up) / 2;
                if (matrix[midV][midH] == target) return true;
                if (matrix[midV][midH] < target) {
                    up = midV;
                    left = midH;
                } else {
                    down = midV;
                    right = midH;                
                }
            }
            if (matrix[up][left] == target) return true;
            if (matrix[down][right] == target) return true;
            return search(matrix, target, upOld, up, right, rightOld) || search(matrix, target, down, downOld, leftOld, left);
        }
    }

Log in to reply
 

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