ArrayList BinarySearch

Question

question

I want to implement a BinarySearch method myself on an Object of Klant how do i do this? Klant has some variables.

public class Klant {
public String klantID;
private String voornaam;
private String tussenvoegsel;
private String achternaam;
private int leeftijd;
private static boolean MAN = true;
private String plaats;
private String email;
/*
 *  Getters and setters included 
 */
}

Klant toevoeging = new Klant("FirstName", "middleName", "\Lastname\"", 20, false, "Location", "[email protected]");
klanten.add(toevoeging);

Answer 1

Using Collections.binarySearch(...)

When you run a Collections.binarySearch(...); on a list the objects in that list must either implement Comparable, or you will have to pass a Comparator into the binarySearch(...) method;

Using a Comparator as an example you could do the following;

class KlantComparator implements Comparator<Klant> {
    @Override
    public int compare(Klant o1, Klant o2) {
        if(condition)
          return 1;
        else if(condition2)
          return 0;
        else 
          return -1;
    }
}

In the above you compare the Klant objects o1 and o2 and return 1 if o1 should be ranked higher than o2, return 0 if they are the same, and return -1 if o1 is ranked lower than o2. And then to run the binary search;

    KlantComparator kc = new KlantComparator();
    ArrayList klants = new ArrayList<Klant>();
    Klant o = new Klant();
    klants.add(o);
    klants.add(new Klant());
    klants.add(new Klant());
    Collections.sort(klants, kc);
    Collections.binarySearch(klants, o, kc);

In the above please note that the klants collection needs to be sorted first, and that the binarySearch needs to be performed using the same Comparator that sorted the list.

I hope this helps.

Further Reading;

• Collections API - binarySearch()
• Comparator API
• Comparable API

Answer 2

Since you want to implement it yourself, Collections.binarySearch isnt good enough for you?

Okay....

Binary Search:

you have a sorted list. Get the element in the middle and compare with the Object in question. if it is lower than the element you want to find, repeat the search in the part of the list, which has only higher elements. If it is higher, search in the list part with only lower elements.

So how do you do binary search?

You need a measure, which defines for 2 object what the lower one and what the higher one is.

Your object must implement Comparable or you must define a Comparator for your list.

Then you need to actually sort the list. Sorting would be Collections.sort(myList).

Now List has the size() method, which will help you determine the first "middle" element.

Pseudocode :

 **input** : keyElement

 startIndex = 0;
 endIndex = list.size();

 midIndex = (endIndex+startIndex) / 2;
 while(list.get(midIndex) !=  keyElement) {
     if (list.get(midIndex) < keyElement) {
         startIndex = midIndex;
     } else {
         endIndex = midIndex;
     }
     midIndex = (endIndex+startIndex) / 2;
 }

 return midIndex;

Something along those lines (be careful with boundaries here... maybe a +/-1 is needed.)