クアッド・パーティション・マトリックス・サーチ

Question

私が持っているプログラムは、与えられた値を見つけるまで、マトリックスを4つの象限に連続して分割することになっています。現在のプログラムでは、それは永遠に実行されます。検索する番号を投稿するにはどうすればよいですか？

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でnumberが見つかった場合、残りの部分は検索されません（yay！）。ご質問がある場合はお知らせください。コードは、最も美しくない、または最適化されていないので、ちょっと私がやっていることを理解できるように、ちょっと残しました。 （非常に基本的な）テストを含む完全なクラスは、... INT [] []行列の要素のための有効なアサーション

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 :("); 
    } 
}