用於二進制搜索的排序數組

我有一個對象數組（電話號碼簿條目，以Entry(surname,initials,extension)的形式存儲），我希望能夠高效地進行搜索。爲了做到這一點，我試圖使用Arrays.binarySearch()。我有兩種單獨的搜索數組的方法，一種使用名稱，另一種使用數字。按照字母順序將數組按姓氏排序，因爲我在我的addEntry()方法的正確位置插入每個元素。按姓名搜索時，我可以使用binarySearch()，因爲數組按字母順序排序，但是我遇到的問題是數組在按數字搜索時未排序。我在Entry類中覆蓋compareTo()來比較姓氏，但是當我按數字搜索時，我需要按照數字的升序對我的數組進行排序，但我不確定如何執行此操作？用於二進制搜索的排序數組

public int lookupNumberByName(String surname, String initials) { 

    int index = 0; 
    if (countElements() == directory.length) { 
     Entry lookup = new Entry(surname, initials); 
     index = Arrays.binarySearch(directory, lookup); 
    } 
    else if (countElements() != directory.length) { 
     Entry[] origArray = directory; 
     Entry[] cutArray = Arrays 
       .copyOfRange(directory, 0, countElements()); 
     directory = cutArray; 
     Entry lookup = new Entry(surname, initials); 
     index = Arrays.binarySearch(directory, lookup); 
     directory = origArray; 
    } 
    return index; 
}

我想爲我的LookupByNumber()方法做這樣的事情 -

public int LookupByNumber(int extension) { 
    Entry[] origArray1 = directory; 
    Entry[] cutArray1 = Arrays.copyOfRange(directory, 0, countElements()); 
    directory = cutArray1; 
    Arrays.sort(directory); //sort in ascending order of numbers 
    Entry lookup1 = new Entry(extension); 
    int index1 = Arrays.binarySearch(directory, lookup1); 
    String surname1 = directory[index1].getSurname(); 
    String initals1 = directory[index1].getInitials(); 
    directory = origArray1; 

    int arrayPos = lookupNumberByName(surname1,initials1); 

    return arrayPos;

我compareTo方法 -

public int compareTo(Entry other) { 
    return this.surname.compareTo(other.getSurname()); 
}

幫助非常感謝

編輯 - 我知道數組不是最好的數據結構，但我哈哈我們已經被特意要求爲這個任務使用一個數組。

更新 - sort(T[] a, Comparator<? super T> c)的工作原理是什麼？當我嘗試寫我自己的Comparator -

public class numberSorter implements Comparator<Entry> { 
@Override 
public int compare(Entry o1, Entry o2) { 
    if (o1.getExtension() > o2.getExtension()) { 
     return 1; 
    } 
    if (o1.getExtension() == o2.getExtension()) { 
     return 0; 
    } 
    if (o1.getExtension() < o2.getExtension()) { 
     return -1; 
    } 
    return -1; 
} 
}

，並呼籲Arrays.sort(directory,new numberSorter());我得到下面的異常 -

java.lang.NullPointerException 
at java.lang.String.compareTo(Unknown Source) 
at project.Entry.compareTo(Entry.java:45) 
at project.Entry.compareTo(Entry.java:1) 
at java.util.Arrays.binarySearch0(Unknown Source) 
at java.util.Arrays.binarySearch(Unknown Source) 
at project.ArrayDirectory.LookupByNumber(ArrayDirectory.java:128) 
at project.test.main(test.java:29)

我究竟在做什麼錯？

來源

2014-04-20 Nick

與其將Entry對象保存在數組中，請將它們保存在Maps中。例如，您將有一個將Surname映射到Entry的Map，另一個將擴展映射到Entry。然後，您可以通過在適當的Map上調用get（）方法來有效地查找Surname或Extension的條目。

如果Map是TreeMap，則查找速度與二進制搜索（O log（n））大致相同。如果您使用HashMap，一旦獲得大量條目，速度可能會更快。

來源

2014-04-20 23:39:53

用於二進制搜索的排序數組

回答

相關問題