Index Out of Bounds Exception in Binary Search

Question

I'm confused at exactly where this happens. I've traced this simple code out on paper as well as used the computer but I can't figure out. In my example I created an array of {1, 2, 3, 4, 5} and it came up with this error for numbers 4 and 5. It worked fine for numbers 1, 2, and 3, as well as numbers not in the array. Can anyone help, please?

public static int search(int[] ar, int num)
{
    int low=0;
    int hi=ar.length-1;
    int mid=(low+hi/2);
    while(hi>=low || mid<=low || mid>=hi )
    {
        if(ar[mid]==num)
        {
            return mid;
        }
        else if(ar[mid]>num)
        {
            hi=mid-1;
            mid=(low+hi/2);
        }
        else
        {
            low=mid+1;
            mid=(low+hi/2);
        }
    }
    return -1;
}

any chance you could post on which line the out-of-bounds is occurring? — mfsiega
– mfsiega, Commented Mar 18, 2012 at 20:16
Are you sure about coniditions mid <= low ? May be mid <= hi && mid >= low ? — kenota
– kenota, Commented Mar 18, 2012 at 20:19
put in a lot of prints and see how your code is going along in decisions. — j13r
– j13r, Commented Mar 18, 2012 at 20:20
changing the or to and didn't change anything. And can you clarify that, j13r? What exactly do you mean? — frozenxdreamer
– frozenxdreamer, Commented Mar 18, 2012 at 20:27

Ashwinee K Jha · Accepted Answer · 2012-03-18 20:24:58Z

3

mid=(low+hi/2);

You need to use prantheses so that you divide after adding low and hi.

mid=(low+hi) / 2;

Also your loop condition should not allow mid to be >high because then it won't termintate for large number not in the array.

answered Mar 18, 2012 at 20:24

Ashwinee K Jha

9,3572 gold badges27 silver badges20 bronze badges

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

2 Comments

frozenxdreamer Over a year ago

Thanks for pointing this out! I always seem to miss the stupidest little things. But now it can't find the highest number? I'll go see if I made any other stupid mistakes.

Ashwinee K Jha Over a year ago

@frozenxdreamer As suggested by others try adding few print statements and see the execution of program that will help more than mentally tracing the steps. You can also make use of debugger of your IDE.

Ted Hopp · Accepted Answer · 2012-03-18 20:23:11Z

0

The problem is the condition under which you continue looping. Try changing this:

while (hi>=low || mid<=low || mid>=hi) {

to this:

while (hi>=low) {

If hi < low, you do not want to continue the loop regardless of the other two conditions (one of which will always be true, I think, if hi < low).

answered Mar 18, 2012 at 20:23

Ted Hopp

235k48 gold badges412 silver badges533 bronze badges

Collectives™ on Stack Overflow

Index Out of Bounds Exception in Binary Search

2 Answers 2

2 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

2 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related