While loop doesnt end in iterative binary search

Question

I'm currently writing a binary search that uses iteration instead of recursion and its not returning anything. I've debugged it down to the while loop not ending but I can't seem to figure out where I went wrong.

Here is the code:

public static <E extends Comparable> boolean binarySearchIterative(E[] array, E obj) {
    int first = 0;
    int last = array.length - 1;
    while(first <= last) {
        int middle = (first + last) / 2;
        if(array[middle].equals(obj)) return true;
        else if(obj.compareTo(array[middle]) < 0) first = middle - 1;
        else first = middle + 1;
    }
    return false;
}

And yes, my list is ordered ;)

doesn't integer division always truncate the remainder? In that case middle + 1 would never become greater than last — Dragondraikk
– Dragondraikk, Commented Jul 7, 2015 at 15:10
Your statement in else if should be last = middle -1; Not first. — Codebender
– Codebender, Commented Jul 7, 2015 at 15:11

Anand S Kumar · Accepted Answer · 2015-07-07 15:12:12Z

3

In the second else if part you need to set last instead of first -

else if(obj.compareTo(array[middle]) < 0) last = middle - 1;

answered Jul 7, 2015 at 15:12

Anand S Kumar

91.4k18 gold badges196 silver badges179 bronze badges

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

Collectives™ on Stack Overflow

While loop doesnt end in iterative 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