卡住 - 我自己實現的多維二進制搜索

Question

我有點卡在我自己的2D數組二進制搜索的實現。它似乎沒有迭代到下一行並保留在同一列（因此是一個永無止境的循環）。二進制搜索的工作方式是從兩個端點（低端和高端點）之間的中間開始。如果查詢太低，則將高端點重新調整爲中點 - 1.如果查詢太高，則將低端點設置爲中點端點+1。所有這些都會發生，直到查詢被找到，或者沒有匹配，從而導致O（log n）的最壞情況。但是，我似乎無法讓數組逐行去搜索值。這是我迄今爲止所做的：

public static int count(int[][]array, int query) { 

     int countoccurences = 0;   
     int low = 0;       
     int high = array[0].length - 1; 
     for (int row = 0; row < array.length; row++) { 
      for (int column = 0; column < array[row].length; column++) { 
       while (low <= high) { 

        int mid = (low + high)/2; //Set mid point to be (low + high) divided by 2 
        if (array[row][mid] == query) { //Check if middle value in each column is equal to the search query 
          countoccurences++; //If it is, increment countoccurences by 1 
         } else if (array[row][mid] < query) { 
          low = mid + 1; //If it is less than query then re-adjust low to be mid index + 1 
         } else {       
          high = mid - 1; //if query is too low, re-adjust high to be mid index - 1 
         } 
       } 
      } 
     } 


     return countoccurences; 


    } 



    public static void main(String[] args) { 
     int[][] array = { {7, 4, 3, 5, 10},{8, 5, 4, 6, 11},{10, 10, 8, 10, 13}, {11, 10, 15, 10, 14}}; 
     System.out.println("Total occurences of the number 10 is: " + count(array, 10)); 
    } 


} 

謝謝！

Answer 1

我認爲你需要像

public static int count(int[][] array, int query) 
    { 
     // nothing to find in an empty array 
     if(array.length == 0) 
      return 0; 

     int countoccurences = 0; 
     for (int column = 0; column < array[0].length; column++) 
     { 
      int low = 0; 
      int high = array.length - 1; 
      while (low <= high) 
      { 
       int mid = (low + high)/2; //Set mid point to be (low + high) divided by 2 
       if (array[mid][column] == query) 
       { 
        // Check if middle value in each column is equal to the search query 
        for (int row = low; row <= high; row++) 
        { 
         if (array[row][column] == query) 
          countoccurences++; //If it is, increment countoccurences by 1 
        } 
        break; 
       } 
       else if (array[mid][column] < query) 
       { 
        low = mid + 1; //If it is less than query then re-adjust low to be mid index + 1 
       } 
       else 
       { 
        high = mid - 1; //if query is too low, re-adjust high to be mid index - 1 
       } 
      } 

     } 
     return countoccurences; 
    } 

重要的變化：

• 換行和列，以實際排序方向匹配的情況下，當介紹break;數據

• 的列中有查詢。這是無限循環的在你的代碼的原因

• 除去外for (int column = 0; column < array[row].length; column++)因爲它沒有任何意義

• ，另一方面，增加內for (int row = low; row <= high; row++)。它應該包含在同一行中有多個目標值的情況，例如數據中的第3列。這個內部循環也可以使用更有效的二進制搜索，但我太懶惰了。