java - 四分区矩阵搜索

Question

我的程序应该将矩阵连续分为四个象限，直到找到给定值。使用当前程序，它会永远运行。如何让它发布我搜索的号码？

 public static void DivideAndConquerSearch(int target, int fromRow, int toRow, int fromCol, int toCol, int[][] matrix, int comparison_counter) {
    boolean found = false;

    while (!found) {

        int i = fromRow + (toRow - fromRow) / 2;
        int j = fromCol + (toCol - fromCol) / 2;

        if (matrix[i][j] == target) {
            found = true;
        } else if (matrix[i][j] < target) {
            if (i + 1 <= toRow) {
                found = false;
                DivideAndConquerSearch(target, i + 1, toRow, fromCol, toCol, matrix, comparison_counter);
            } else if (j - 1 >= fromCol) {
                found = false;
                DivideAndConquerSearch(target, fromRow, toRow, fromCol, j - 1, matrix, comparison_counter);
            }
        }
        comparison_counter++;
    }
    if (found == true) {
        System.out.println(target + " found in " + comparison_counter + " comparisons using recursive search");
    } else {
        System.out.println(target + " NOT found in " + comparison_counter + " comparisons using recursive search");
    }

}

Answer 1

我写了一些使用递归方法简单地搜索整个数组(强力类型)的东西。它将 2D 数组分成 4 个象限并搜索 NW、NE、SW、SE。我使用 OR 条件来检查是否在任何象限中找到它。因此，如果在 NW 中找到数字，它将不会搜索其余的(耶!)。如果您有任何疑问，请告诉我。该代码不是最漂亮或最优化的，我有点选择保留这种方式，以便您可以更好地理解我在做什么。完整的类(class)，包括(非常基本)测试...

public class Divide_Conquer_2dArr {

    private static boolean divideAndConquer(int[][] arr, int target) {

        /* IDEA */
        // NORTH_WEST [Kanye West joke(?)]
        // need to search row-wise from [0,row-1], col-wise from [0, col-1]

        // NORTH_EAST
        // need to search row-wise from [0,row-1], col-wise from [col, maxCol]

        // SOUTH_WEST
        // need to search row-wise from [row, maxRow], col-wise from [0, col-1]

        // SOUTH_EAST
        // need to search row-wise from [row, maxRow], col-wise from [col, maxCol]

        return divideAndConquerHelper(arr, target, 0, arr[0].length-1, 0, arr.length-1);
    }

    private static boolean divideAndConquerHelper(int[][] arr, int target, int minCol, 
            int maxCol, int minRow, int maxRow) {
        // print relevant stuff
        printArr(arr,  minCol, maxCol, minRow, maxRow);

        if(minCol == maxCol || minRow == maxRow) {

            if(minCol == maxCol) {
                for(int i = minRow ; i <= maxRow ; i++)
                    if(arr[i][minCol] == target) {
                        System.out.println("Found!");
                        return true;
                    }
            }

            else if(minRow == maxRow) {
                for(int i = minCol ; i <= maxCol ; i++)
                    if(arr[minRow][i] == target) {
                        System.out.println("Found!");
                        return true;
                    }
            }

            return false;
        }

        int midRow = (maxRow + minRow)/2;
        int midCol = (maxCol + minCol)/2;


        return 
                // north-west quadrant
                divideAndConquerHelper(arr, target, minCol, midCol, minRow, midRow)
                ||
                // north-east quadrant
                divideAndConquerHelper(arr, target, midCol+1, maxCol, minRow, midRow)
                ||
                // south-west quadrant
                divideAndConquerHelper(arr, target, minCol, midCol, midRow+1, maxRow)
                ||
                // south-east quadrant
                divideAndConquerHelper(arr, target, midCol+1, maxCol, midRow+1, maxRow);
    }

    // prints arr[minRow..maxRow][minCol..maxCol] inclusive
    private static void printArr(int[][] arr, int minCol, 
            int maxCol, int minRow, int maxRow) {
        for(int i = minRow ; i <= maxRow ; i++ ) {
            for(int j = minCol ; j <= maxCol ; j++) {
                System.out.print(arr[i][j] + "\t");
            }
            System.out.println();
        }
        System.out.println("==================================");
    }

    public static void main(String[] args) {
        int[][] arr = new int[][]
                {
                    {1,2,3,4},
                    {6,7,8,9},
                    {11,12,13,14},
                    {16,17,18,19},
                    {21,22,23,24}
                };

        boolean retVal = divideAndConquer(arr, 12);
        if(!retVal)
            System.out.println("Not found :(");
    }
}