在二維數組中按二進制搜索元素（具有重複項目）按列順序排序？

Question

編輯：

對於2D陣列，僅柱進行分選但沒有排序的行。下面是我寫的方法，首先在每列中進行二進制搜索，然後遍歷每一列並計算重複元素。但是代碼對我不起作用。有人可以幫助我嗎？非常感謝！

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

    int count = 0; 

    for (int j = 0; j < array[0].length; j++) { 
     count += biSearch(array, query, j); 
    } 

    return count; 
} 

private static int biSearch(int[][] array, int searchItem, int row) { 

    // create a 1D array to hold the entries of 2D array's column 
    int[] column = new int[array.length]; 
    int count = 0; 
    int low = 0; 
    int high = column.length - 1; 

    // put 2D array's column into 1D array 
    for (int i = 0; i < array.length; i++) 
     column[i] = array[i][row]; 

    // binary search on column array 
    while (low < high) { 
     int mid = (low + high)/2; 

     if (column[mid]== searchItem) { 
      while ((mid - 1) >= 0) { 
       if (column[mid - 1] == searchItem){ 
        mid--; 
        count++; 
       } 
      } 
      while ((mid + 1) < (column.length - 1)) { 
       if (column[mid + 1] == searchItem){ 
        mid++; 
        count++; 
       } 
      } 
     } 
     else if (column[mid] > searchItem) 
      high = mid - 1; 
     else if (column[mid] <searchItem) 
      low = mid + 1; 
    } 

    return count; 
} 

Answer 1

不知道如果這是唯一的問題，但是這個代碼是錯誤的：

if (column[mid]== searchItem) { 
    while ((mid - 1) >= 0) { 
     if (column[mid - 1] == searchItem){ 
      mid--; 
      count++; 
     } 
    } 
    while ((mid + 1) < (column.length - 1)) { 
     if (column[mid + 1] == searchItem){ 
      mid++; 
      count++; 
     } 
    } 
} 

它主要測試從mid的column陣列的所有元素0和不同於0到column.length-1。不僅你通過了整個數組，這違背了你的二分查找的目的，你訪問了mid和0兩次之間的所有元素，這意味着你的計數是錯誤的。

在更好的方法：

if (column[mid]== searchItem) { 
    count = 1; 
    int temp = mid; 
    while (temp > 0 && column[temp - 1] == searchItem) { 
     temp--; 
     count++; 
    } 
    temp = mid; 
    while (temp < column.length - 1 && column[temp + 1] == searchItem) { 
     temp++; 
     count++; 
    } 
} 

的兩點需要注意：

1. 我不修改mid，因爲我們需要的mid第二while循環的初始值。

2. 當我遇到不等於searchItem的元素時，我退出每個while循環。由於數組應該被排序（否則二進制排序將不起作用），因此不需要遍歷整個數組。

P.S.在您的biSearch中名爲row的參數實際上是您的二維數組列的索引，因此它的名稱很混亂。