Java Binary search

Question

Hi there, Trying to perform a binary search on a sorted array of Book objects.

Its not working well, it returns the correct results for some of the objects, but not all.

I went through the loop on paper and it seems that a number can get missed out due to rounding #.5 upwards.

Any ideas how to make this work?

Book found = null;
    /*
     * Search at the center of the collection. If the reference is less than that,
     * search in the upper half of the collection, else, search in the lower half.
     * Loop until found else return null.
     */
    int top = numberOfBooks()-1;
    int bottom = 0;
    int middle;
    while (bottom <= top && found == null){
        middle = (bottom + top)/2;
        if (givenRef.compareTo(bookCollection.get(middle).getReference()) == 0) {
            found = bookCollection.get(middle);
        } else if (givenRef.compareTo(bookCollection.get(middle).getReference()) < 0){
            bottom = middle + 1;
        } else if (givenRef.compareTo(bookCollection.get(middle).getReference()) > 0){
            top = middle - 1;
        }
    }
    return found;

Answer 1

What about Collections.binarySearch()?

Answer 2

A couple suggestions for you:

• there's no need to keep a Book variable. In your loop, just return the book when it's found, and at the end return null. And you can also remove the boolean check for the variable in the while condition.

• the middle variable can be scoped inside the loop, no need to have it live longer.

• you're doing bookCollection.get(middle).getReference() three times. Consider creating a variable and then using it.

• the middle = (bottom + top)/2 is a classic mistake in binary search implementation algorithms. Even Joshua Bloch, who wrote the Java Collection classes, made that error (see this interesting blog post about it). Instead, use (bottom+top) >>> 1, to avoid integer overflow for very large values (you probably wouldn't encounter this error, but it's for the principle).

As for your actual problem statement, rounding would be downwards (integer division), not upwards. To troubleshoot the problem:

• are you sure the numberOfBooks() method corresponds to the length of your collection?
• are you sure the compareTo() method works as expected for the types you are using (in your code example we do not know what the getReference() return type is)
• are you sure your collection is properly sorted according to getReference()?
• and finally, are you sure that using givenRef.compareTo(bookCollection.get(middle).getReference()) < 0 is correct? In standard binary search implementations it would be reversed, e.g. bookCollection.get(middle).getReference().compareTo(givenRef) < 0. This might be what donroby mentions, not sure.

In any case, the way to find the error would be to try out different values and see for which the output is correct and for which it isn't, and thus infer what the problem is. You can also use your debugger to help you step through the algorithm, rather than using pencil and paper if you have to run many tests. Even better, as donroby said, write a unit test.

Answer 3

All of JRL's suggestions are right, but the actual fail is that your compares are reversed.

I didn't see this immediately myself, but replicating your code into a function (using strings instead of Books), writing a some simple Junit tests and then running them in the debugger made it really obvious.

Write unit tests!

Answer 4

I found the problem.

It turns out i was binary searching my bookCollection arrayList, and NOT the new sroted array i had created - sortedLib.

Silly mistake at my end, but thanks for the input and suggestions!