二進制搜索按列排序的二維數組只搜索第一列

Question

因此，我對編程非常陌生，我試圖將二分搜索算法應用於按列排序的二維數組。我的程序只能在第一列正確執行，所以我認爲它陷入了無限循環。這個問題似乎在我while循環中的第二個else語句中，但是我完全不知道這個問題可能是什麼。

public static void main(String[] args) { 
    // TODO Auto-generated method stub 

    int[][] array = { {5, 8, 10, 6}, 
      {20, 10, 20, 15}, 
      {20, 15, 25, 20}, 
      {20, 20, 32, 25} }; 
    int query = 20; 

    int search_status; 
    search_status = count(array, query); 
    System.out.println(query + " occurred " + search_status + " times"); 

} 

public static int count(int[][]array, int query){ 
    int count = 0; 
    int low = 0; 
    int high = array.length - 1; 
    for (int c = 0; c < array[0].length; c++) { 
     while (low <= high) { 
      int mid = low + (high - low)/2; 

      if (array[mid][c] > query) { 
       high = mid - 1; 
      } 
      else if (array[mid][c] < query) { 
       low = mid + 1; 
      } 
      else if (array[mid][c] == query) { 
       count++; 
       int up = -1; 
       int down = 1; 
       while ((mid + up >= 0) && (array[mid + up][c] == query)) { 
        up--; 
        count++; 
       } 
       while ((mid + down <= array.length - 1) && (array[mid + down][c] == query)) { 
        down++; 
        count++; 
       } 
       return count; 
      } 
     } 
    } 
    return - 1; 
} 

}

Answer 1

嘗試推入列第一行的這種做法：

public static void main(String[] args) { 
    // TODO Auto-generated method stub 

    int[][] array = { {5, 8, 10, 6}, 
      {20, 10, 20, 15}, 
      {20, 15, 25, 20}, 
      {20, 20, 32, 25} }; 
    int query = 20; 

    int search_status = 0; 

    for (int c = 0; c < array.length; c++) 
     search_status += count(array, query, c); 

    System.out.println(query + " occurred " + search_status + " times"); 

} 

public static int count(int[][]array, int query, int row){ 
    int[] column = new int[array.length]; 
    int count = 0; 
    int low = 0; 
    int high = column.length - 1; 

    for (int i = 0; i < array[row].length; i++) 
     column[i] = array[i][row]; 

    while (low <= high) { 
     int mid = low + (high - low)/2; 

     if (column[mid] > query) { 
      high = mid - 1; 
     } 
     else if (column[mid] < query) { 
      low = mid + 1; 
     } 
     else if (column[mid] == query) { 
      int mover = -1; 
      int counted = 1; 

      // Go all the way down 
      while ((mid + mover >= 0) && (column[mid + mover] == query)) 
      { 
       mover--; 
       counted++; 
      } 

      mover+=counted+1; 
      count+=counted; 

      while ((mid + mover <= column.length - 1) && (column[mid + mover] == query)) 
      { 
       mover++; 
       count++; 
      } 

      return count; 
     } 
    } 

    return 0; 
} 

編輯：稍微好一點的實現，以免重複計算。