如何在通用程序中實現二進制搜索對象數組？

因此，我正在學習java課程，並且正在學習排序，搜索，算法和泛型。我試圖重新創建一個二分查找方法/類，它接受任何類型的Comparable對象（如ArrayList < 類型>）。如何在通用程序中實現二進制搜索對象數組？

我明白如何去做int s，但我真的不知道如何去處理它與非原始類型。這是我認爲它應該大致是這樣的：

public class Objects<T> implements Comparable //I'm not sure about this, 
//but I need to call compareTo() to compare the objects? 
{ 
    /** 
    * called from other program to find an element index in an array 
    */ 
    public static int binSearchAll(T find, T array[]) 
    { 
     return binarySearch(array, 0, (array.length)-1, find); 
    } 

    public static int binarySearch(T array[], int lower, int upper, T X) 
    //x is the element to find 
    { 
     if (upper < lower) 
      return -1; 
     int middle = (lower + upper)/2; 
     if (array[middle].compareTo(X)) 
      return middle; 
     if (array[middle] < X) 
      return binarySearch(a, middle+1, upper, X); 
     else 
      return binarySearch(a, lower, middle-1, X); 
    } 
}

我試圖弄清楚如何使這項工作，但我不知所措。在int版本中，它可以正常工作，但只適用於integer類型，並且不會接受double或string類型，如問題所述。

在驅動程序類

，我希望能夠創建一個新的對象，並使用它像這樣：

String[] str = {"a", "b", "c"}; 
Objects<String> s = new Objects<String>(); 
int indexOfB = s.binSearchAll("b", str);

或者，如果可能的話，像這樣：

String[] str = {"a", "b", "c"}; 
int indexOfB = Object<String>.binSearchAll("b", str);

確切措辭的問題是：

創建一個ObjectBinarySearcher類，可以搜索Comparable對象的數組。在程序中演示該類，該程序在String 對象的數組中搜索字符串。

我幾乎可以肯定，我正在推翻這一點。

感謝您的幫助！

來源

2013-03-30 user2005078

這兩條線是問題：

if (array[middle].compareTo(X)) 
... 
if (array[middle] < X)

... compareTo返回int，而不是boolean，你不能在任意類型使用<。我懷疑你已經意識到這一點，但我只是給你一個提示：閱讀Comparable.compareTo文檔。您需要使用compareTo而不是< ...請閱讀返回值的文檔以瞭解您需要執行的操作。

（你可能只是想打電話compareTo一次，然後檢查結果的兩倍。有三種可能性來考慮，如記錄...）

來源

2013-03-30 17:00:43

謝謝，我沒有閱讀Comparable類的正確的文檔，現在我工作。我認爲它與Object.equals（）方法類似。 – user2005078

你需要你的模板類T實現Comparable接口。你的實際代碼意味着只有你的Objects類實現了接口。您必須打開

public class Objects<T> implements Comparable { 
    //class content... 
}

進入

public class Objects<T extends Comparable<T>> { 
    //class content... 
}

而且也遵循JonSkeet's answer約compareTo方法的建議。

來源

2013-03-30 17:00:58

謝謝，我只是在學習，所以我沒有意識到發生了什麼事情。我也很困惑，爲什麼當我調用compareTo（）方法時，我一直在收到錯誤，現在我明白它必須在類中被覆蓋才能使用，除非數據類型已經覆蓋它。我現在有它的工作。 – user2005078

@ user2005078因爲你是新來的人，不要忘記標記最好的帖子作爲答案，點擊代表下方的檢查。如果兩個答案都滿足你，你可以發佈一個新答案並接受它。 –

，仍然無法正常工作。它需要'T延伸可比' – newacct

您需要您的模板類T實現可比較的接口。你的實際代碼意味着只有你的Objects類實現了這個接口。您必須打開
public class Objects<T> implements Comparable { 
    //class content... 
} 
進入
public class Objects<T extends Comparable<T>> { 
    //class content... 
} 
Luiggi Mendoza

而且......

這兩條線是問題：如果（數組[中]。 compareTo（X））... if（array [middle] < X）... compareTo返回int而不是布爾值，並且您不能在上使用<任意類型。我懷疑你已經意識到這一點，但我只是給你一個提示：閱讀Comparable.compareTo文檔。您需要以使用compareTo而不是< ...請閱讀返回值的文檔以確定您需要執行的操作。

（你可能只是想調用一次的compareTo，然後檢查結果的兩倍。有三種可能性要考慮，記錄...） Jon Skeet

感謝您的答案。結合起來，我設法讓程序工作。它現在的作品：

String[] str = {"a", "b", "c"}; 
Objects<String> s = new Objects<String>(); 
int indexOfB = s.binSearchAll("b", str);

來源

2013-04-01 04:45:50 user2005078

如何在通用程序中實現二進制搜索對象數組？

回答

相關問題