Sorting array for Binary Search

Question

I have an array of objects (telephone directory entries, stored in the form Entry( surname,initials,extension) ) which I would like to search efficiently. In order to do this I'm trying to use Arrays.binarySearch(). I have two separate methods for searching the array, one using names and the other using numbers. The array is sorted by Surname in alphabetical order as I insert each element in the correct place in my addEntry() method. I can use binarySearch() when searching by name as the array is sorted in alphabetical order, but the problem I have is the array is not sorted when I search by number. I have overridden compareTo() in my Entry class for comparing surnames, but when I search by number I need to sort my array in ascending order of numbers, I am unsure how to do this?

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;
}

I would like to do something like this for my LookupByNumber() method -

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;

My compareTo method -

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

Help very much appreciated

edit - I realize arrays are not the best data structure for this, but I have been specifically asked to use an array for this task.

Update - How exactly does sort(T[] a, Comparator<? super T> c) work? when I try writing my own 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;
}
}

And calling Arrays.sort(directory,new numberSorter()); I get the following exception -

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)

What exactly am I doing wrong?

Warren Dew · Accepted Answer · 2014-04-20 23:39:53Z

2

Rather than keeping the Entry objects in Arrays, keep them in Maps. For example, you'd have one Map that mapped the Surname to the Entry, and another that mapped the Extension to the Entry. You can then efficiently look up the entry by Surname or Extension by calling the get() method on the appropriate Map.

If the Map is a TreeMap, the lookup is about the same speed as a binary search (O log(n)). If you use a HashMap, it can be even faster once you get a large number of entries.

answered Apr 20, 2014 at 23:39

Warren Dew

8,9383 gold badges34 silver badges44 bronze badges

Sign up to request clarification or add additional context in comments.

Collectives™ on Stack Overflow

Sorting array for Binary Search

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related