Binary searching an object array for the field of an element

Question

Is there anyway to search a binary array of Objects, not for a complete element of the array, but rather for an element containing a specific field value? At present the only way I see of doing it is to create a new "Entry" object to search for - and because of the compareTo implementation it doesnt matter what the second field "intial" contains.

Is there a way of implementing a binary search so that I can simply search surname.element fields directly - given that the array is already sorted by surname?

I am aware that I could iterate through the array searching the fields of each element but in this case I need to use a binarySearch.

public class Entry implements Comparable<Entry> { //implements allows sorting
    public String surname;
    public char intial;

 public Entry(String surname, String initial, int number) {
    this.surname = surname.toUpperCase();
    this.intial = initial.toUpperCase().charAt(0); // if whole name entered 
                                                   //takes first letter only

}

@Override
public int compareTo(Entry o) {

    else {
        return this.surname.compareTo(o.surname);
    }

}

public class EntryList {

    public static main(String[] args) {

    List<Entry> directory = new ArrayList<Entry>(); 

    directory.add(new Entry("surname", "intial")); 
            int i = Collections.binarySearch(directory, new Entry("surname", " ")); //doesnt matter whats in intial field
    }
}


}

poroszd · Accepted Answer · 2014-02-22 22:51:57Z

1

Your question doesn't make much sense.

Binary search works on sorted collection, so of course your element have to be comparable. Define your compareTo and equals methods to consider only the surname field, and then you can use binarySearch.

EDIT: I'm still not sure whether you are asking about the usage of the library function binarySearch or about the implementation of a custom binary search function.

For the first case the answer is no, there is no such overloading of binarySearch in the API. Generally in an array you want to search by entity equality, because in the intended use case of this method you already have the entity you are searching for, but you don't know if it is contained in the target array, and on which index can be found. However you want to search an entity by a key, which might sign that you are misusing ArrayList and binarySearch; a SortedMap would fit better for this task.

On the other hand, if you stick to ArrayList, than of course you can implement yourself a method like binary search, which uses only your surname field for matching.

edited Feb 22, 2014 at 22:51

answered Feb 21, 2014 at 22:51

poroszd

5925 silver badges12 bronze badges

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

4 Comments

davidhood2 Over a year ago

Thanks for your comment - especially about the useless line of code. To rephrase a badly worded question (apologies for that) - assuming equals and compareTo methods are already overwritten to only consider the "surname" field, is there a way of implementing .binarySearch w/out creating a new Entry object as the second argument?

poroszd Over a year ago

@davidhood2 Edited my answer in response.

user4998958 Over a year ago

@poroszd Instead of implementing the binary search directly you could instead implement a method that is a facade to the binarySearch in the standard library. The method would use a private constructor that initialises the object with only the fields being used in the comparison, then calls the binary search. Or am I missing something here?

poroszd Over a year ago

@Wrap2Win No, you are correct, reusing Collections.binarySearch is better than rolling your own implementation.

Collectives™ on Stack Overflow

Binary searching an object array for the field of an element

1 Answer 1

4 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

4 Comments

Your Answer

Sign up or log in

Post as a guest

Related