Binary search implementation java algorithm

Question

I need help with implementing the binary search algorithm, can someone tell me what's wrong with my code:

public int bsearch(Item idToSearch) { 
    int lowerBoundary = 0;
    int upperBoundary = myStore.size() - 1;
    int mid = -1;

    while(upperBoundary >= lowerBoundary) {
        mid = (lowerBoundary + upperBoundary) / 2;

        //if element at middle is less than item to be searched, than set new lower boundary to mid
        if(myStore.get(mid).compareTo(idToSearch) < 0) {
            lowerBoundary = mid - 1;
        } else {
            upperBoundary = mid + 1;
        }
    } //end while loop

    if(myStore.get(mid).equals(idToSearch)) {
        return mid;
    } else {
        return -1; // item not found
    }
} // end method

A debugger could definitely tell you what is wrong.

Sotirios Delimanolis
– Sotirios Delimanolis

2014-03-31 01:42:24 +00:00
Commented Mar 31, 2014 at 1:42 — Sotirios Delimanolis
– Sotirios Delimanolis, Commented Mar 31, 2014 at 1:42
a quite incorrect algorithm...

Pingu
– Pingu

2014-03-31 01:46:30 +00:00
Commented Mar 31, 2014 at 1:46 — Pingu
– Pingu, Commented Mar 31, 2014 at 1:46

locoyou · Accepted Answer · 2014-03-31 01:47:38Z

4

I think you made a mistake when update lowerBoundary and upperBoundary.

It may be:

    if(myStore.get(mid).compareTo(idToSearch) < 0){
        lowerBoundary = mid + 1;
    } else {
        upperBoundary = mid - 1;
    }

And why don't you break the loop if you find the element at mid?

answered Mar 31, 2014 at 1:47

locoyou

1,6971 gold badge15 silver badges20 bronze badges

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

Comments

Peter Lawrey · Accepted Answer · 2014-03-31 04:21:13Z

0

I would

stop when the lower and upper bound are the same.
stop when you find a match
use mid = (hi + lo) >>> 1; to avoid an overflow causing a bug.
read the code in the JDK which does this already as it works correctly.

answered Mar 31, 2014 at 4:21

Peter Lawrey

535k83 gold badges770 silver badges1.2k bronze badges

Comments

Khaled.K · Accepted Answer · 2014-03-31 06:37:05Z

0

The first issue is with the boundaries, also you should stop in case he found the value, but he doesn't which lead to possible overlook.

while(upperBoundary >= lowerBoundary)
{
        mid = (lowerBoundary + upperBoundary) / 2;

        if (myStore.get(mid).equals(idToSearch)) break; // goal

        if(myStore.get(mid).compareTo(idToSearch) < 0)
        {
            lowerBoundary = mid + 1;
        }
        else
        {
            upperBoundary = mid - 1;
        }
}

answered Mar 31, 2014 at 6:37

Khaled.K

5,9801 gold badge35 silver badges52 bronze badges

Collectives™ on Stack Overflow

Binary search implementation java algorithm

3 Answers 3

Comments

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related