BinarySearch Implementation does not work in certain cases

I'm a java beginner and I'm trying to code an implementation of the binary search algorithm.

This is my code:

    protected int doSearch(List<Integer> list, int key) throws SearchException{

        int min = 0;
        int max = list.size()-1;

        while(max > min){
            int mid = min + ((max-min)/2);
            if(list.get(mid)==key){
                return mid;
            }
            else if(list.get(mid) < key){
                min = mid +1 ;
            }
            else{
                max = mid - 1;
            }
        }
        throw new SearchException("");
    }

I tried to copy it from this link http://en.wikipedia.org/wiki/Binary_search_algorithm and tried to get it working for lists.

The input list is [1, 2, 3, 4, 5, 7, 9]

If I search for the key 2 the output is 1 which is fine, but if I try for example 1 the SearchException is fired.

I can't explain why. I tried to debug the code by reproducing it on paper, but it worked on the paper.

Thank you!

Jon Skeet
people
quotationmark

You're currently inconsistent about whether max is an inclusive lower bound, as suggested here:

int max = list.size()-1;
...
max = mid - 1;

or an exclusive lower bound, as suggested here:

while (max > min)

You can make it work either way, so long as you're consistent. Personally I'd suggest using an exclusive upper bound, as that's consistent with things like list.size() and computer science in general. So if mid is too large, you need to change max to equal mid. Your code will look like this:

int max = list.size(); // Note change here

while(max > min) {
    int mid = min + ((max - min) / 2);
    if (list.get(mid) == key) {
        return mid;
    } else if (list.get(mid) < key) {
        min = mid +1 ;
    } else {
        max = mid; // Note change here
    }
}

(I've fiddled with the formatting to make it easier to read IMO as well. See whether you prefer it or not.)

people

See more on this question at Stackoverflow