What is wrong with my java binary search code?

Question

I think I'm in an endless loop in my binary search code. I'm passing in the empID, so it can return the subscript for the mid but its not returning anything.

public int binSearch(int empID)
{
    int first = 0;
    int last = empCount - 1;
    int found = 0;
    int mid = 0;

    while (first <= last && found == 0)
    {
        mid = (first + last) / 2;

        if (empNums[mid] == empID)
        {
            found = 1;
        }
        else
        {   
            if (empNums[mid] < empID)
            {
                first = mid + 1;
            }
            else
            {
                last = mid - 1;
            }
        }
        while (found == 0)
        {
        mid = -1;
        }

    }
    return mid;

}

while (found == 0) mid = -1; you definitely don't want this. — E_net4
– E_net4, Commented Dec 7, 2014 at 0:37

E_net4 · Accepted Answer · 2014-12-07 01:31:28Z

1

I seriously don't understand why you put that while(found==0) loop in the middle of the function, but it is definitely leading to the endless loop. Simply try removing it. In order to know whether a solution was found, we can make the method return -1 in this particular case. This condition only has to be checked at the end of the function. I've also put a logical right bit-shift when calculating your middle index.

public int binSearch(int empID)
{
    int first = 0;
    int last = empCount - 1;
    boolean found = false;
    int mid = 0;

    while (first <= last && !found)
    {
        mid = (first + last) >>> 1; // overflow prevention

        if (empNums[mid] == empID) {
            found = true;
        } else if (empNums[mid] < empID) {
            first = mid + 1;
        } else {
            last = mid - 1;
        }
    }
    return found ? mid : -1;
}

edited Dec 7, 2014 at 1:31

answered Dec 7, 2014 at 0:43

E_net4

30.5k13 gold badges118 silver badges155 bronze badges

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

6 Comments

jaramore Over a year ago

Well I have this flowchart and I'm trying to code the binary search using the flowchart. So when the while loop terminates, we still have to wonder if the part was found. The variable by that name is the answer. If found is still 0, then we have to set mid to -1, since that is the variable we are returning. But if the part was found, then we can just return the value of mid as the subscript of the actual part.

E_net4 Over a year ago

In that case you would want to change while to if and put it outside the main while loop.

jaramore Over a year ago

Oh okay wow. I thought it was a while loop instead of an if statement in the flowchart. Thank you!

E_net4 Over a year ago

I have added a few more tweaks to the code. Please see if this works for you.

Dmitry Over a year ago

@E_net4, I'm not sure, does (first + last) >>> 2 will find a middle? 100 >>> 2 will gyve 25, for example (because 2 bites will be shifted left). One need to use (first + last) >>> 1 to make it half. But I do not really see a benefit in (first + last) >>> 1 comparing with (first + last) / 2

|

click · Accepted Answer · 2014-12-07 00:44:07Z

0

Lets look at this this scenario: Your first is 0 and your end is 1. then you have this: mid = 1+0/2 which is 0 always! this can lead to the problem becasue you can just keep checking a same position over and over again.

Try so use the Math.Ceil method when you are getting your mid:

Mid = Math.Ceil(start+end)/2); P.S you might need to cast!! Good luck

answered Dec 7, 2014 at 0:44

click

4671 gold badge7 silver badges26 bronze badges

1 Comment

E_net4 Over a year ago

Not really. Imagine the array is [1,5] (as you can see, first and last are 0 and 1) and you're searching for 0. last would change to -1, ending the loop. If you were searching for 2, first would change to 1, leaving with the array slice [5]. The position isn't checked infinitely. Also, Math.ceil is definitely not advised here, as it just creates an unnecessary overhead of integer-to-double-to-integer conversions.

Dmitry · Accepted Answer · 2014-12-07 01:12:25Z

I would suggest this:

public int binSearch(int empID)
{
    int first = 0;
    int last = empCount - 1;
    int mid;

    // check the first and last element, otherways it could take too long to get to them
    if (empNums[first] >= empID) 
        mid = first;
    else if (empNums[last] <= empID)
        mid = last;
    else 
        do {
            mid = (first + last) / 2;
            // If you have found an element, just return it, no found variable is required     
            // And you do not want to add or subtract 1 from a limits, because 
            // next element could be one you looking for 
            if (empNums[mid] == empID)
                return mid;
            else if (empNums[mid] < empID)
               first = mid;
            else
                last = mid;
        } while (first < last);

    // optional check to see that correct parameter has been found
    if (empNums[mid] != empID) {
       // do something
    }

    return mid;
}

Collectives™ on Stack Overflow

What is wrong with my java binary search code?

3 Answers 3

6 Comments

1 Comment

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

6 Comments

1 Comment

Comments

Your Answer

Sign up or log in

Post as a guest

Related