Using binarySearch to look for Object in ArrayList

Question

I have a problem with searching for an Object in an ArrayList.

This is my code so far:

public static int binarySearch( ArrayList list, Object key ) {
    Comparable comp = (Comparable)key;

    int res = -1, min = 0, max = list.size() - 1, pos;
    while( ( min <= max ) && ( res == -1 ) ) {
        pos = (min + max) / 2;
        int comparison = comp.compareTo(pos);
        if( comparison == 0)
            res = pos;
        else if( comparison < 0)
            max = pos - 1;
        else
            min = pos + 1;
    }
    return res;
}

And this is my testing:

public static void main(String[] args) {
    ArrayList list = new ArrayList();
    list.add(new String("February"));
    list.add(new String("January"));
    list.add(new String("June"));
    list.add(new String("March"));

    System.out.println(list);

    Object obj = new String("February");

    int index = binarySearch(list, obj);

    System.out.println(obj + " is at index" + index);

}

The program always returns -1, which means that it never finds the object it's searching for? Do you see any error? Or am I testing the search incorrectly?

new String("February") is nonsense. Just write "February". There is no use for constructing a String by passing another String. — Holger
– Holger, Commented Feb 12, 2014 at 15:04

Luiggi Mendoza · Accepted Answer · 2014-02-12 14:39:14Z

2

You're comparing comp against pos which is like comparing a Comparable (in this case, a String) with an Integer:

int comparison = comp.compareTo(pos);

You should, instead, retrieve the element in pos index in the list and use that element to do the comparison:

int comparison = comp.compareTo(list.get(pos));

answered Feb 12, 2014 at 14:39

Luiggi Mendoza

85.9k16 gold badges160 silver badges354 bronze badges

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

3 Comments

theOGloc Over a year ago

Of course, that makes sense! But after the change, I am still receiving -1 even though in this case the index should be 0?

Luiggi Mendoza Over a year ago

@theOGloc I just copied and pasted your code with my change and prints February is at index0. Changed the key to "June" and printed June is at index2. Make sure to save the changes, recompile and re-run your tests.

theOGloc Over a year ago

Yes of course. I realized that I have a custom incomplete ArrayList class which was giving me wrong size of the list. Thanks for the help!

Collectives™ on Stack Overflow

Using binarySearch to look for Object in ArrayList

1 Answer 1

3 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

3 Comments

Your Answer

Sign up or log in

Post as a guest

Related