Use "Divide and Conquer" to solve it


  • 0
    P

    Because the elements are in 2D matrix ascendingly, I can easily determine that target element exists upper half matrix or lower half matrix.

    Time complexity:
    If there is a MxN matrix, the time complexity is O(log M) + O(log N)

        public boolean searchMatrix(int[][] matrix, int target) {
            if (matrix.length == 0 || matrix[0].length == 0)
                return false;
    
            return isExist(0, matrix.length - 1, target, matrix);
        }
    
        private boolean isExist(int startRow, int endRow, int target, int[][] matrix) {
            if (startRow > endRow)
                return false;
    
            int middleRow = startRow + (endRow - startRow) / 2;
            int lastPivot = matrix[middleRow][matrix[0].length - 1];
            int startPivot = matrix[middleRow][0];
    
            if (target == lastPivot || target == startPivot)
                return true;
    
            if (startPivot < target && target < lastPivot)
                return Arrays.binarySearch(matrix[middleRow], target) >= 0;
    
            if (target < lastPivot)
                return isExist(startRow, middleRow - 1, target, matrix);
            else
                return isExist(middleRow + 1, endRow, target, matrix);
        }
    

Log in to reply
 

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