A JAVA recursion solution


  • 0
    A
    class Solution {
        public boolean searchMatrix(int[][] matrix, int target) {
            return Find(target, matrix);
        }
        
        public boolean Find(int target, int [][] array)
        {
            if (array.length == 0)
            {
                return false;
            }
    
            if (array[0].length == 0)
            {
                return false;
            }
            return FindInternal(target, array, 0, 0, array[0].length, array.length);
        }
    
        public boolean FindInternal(int target, int [][] array, int startRow, int startCol, int width, int height)
        {
            if (width <= 0 || height <= 0)
            {
                return false;
            }
    
            if (width == 1 && height == 1)
            {
                return target == array[startRow][startCol];
            }
    
            int rowMove = (height - 1) / 2;
            int colMove = (width - 1) / 2;
    
            int middleRow = startRow + rowMove;
            int middleCol = startCol + colMove;
    
            int leftwidth = 1 + colMove;
            int topHeight = 1 + rowMove;
    
            int rightWidth = width - leftwidth;
            int bottomHeight = height - topHeight;
    
            int middle = array[middleRow][middleCol];
    
            if (target == middle)
            {
                return true;
            }else if (target < middle)
            {
                boolean a = FindInternal(target, array, startRow, middleCol + 1, rightWidth, topHeight);
                if (a)
                    return true;
                boolean b = FindInternal(target, array, middleRow + 1, startCol, leftwidth, bottomHeight);
                if (b)
                    return true;
                return FindInternal(target, array, startRow, startCol, leftwidth, topHeight);
            }else
            {
                boolean a = FindInternal(target, array, startRow, middleCol + 1, rightWidth, topHeight);
                if (a)
                    return true;
                boolean b = FindInternal(target, array, middleRow + 1, startCol, leftwidth, bottomHeight);
                if (b)
                    return true;
                return FindInternal(target, array, middleRow + 1, middleCol + 1, rightWidth, bottomHeight);
            }
    
    
        }
    }
    

Log in to reply
 

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