Via: http://rc3.org/2010/04/25/becoming-a-better-programmer/

I had two bugs in my first implementation: one was a reversed order of operands in “int size = end - start;”, as “int size = start - end;”, and the second was returning “middleValue” instead of “middle”. Otherwise I think it is correct, avoiding the int overflow problem (unintentionally) I believe.

public class BinarySearch {
    public static void main(String[] args) {
        int[] numbers = new int[]{0, 1, 3, 5, 7, 8, 9, 20, 45, 100, 876, 1000, 1001};
        int value = 45;
        System.err.println(“numbers:”);
        for (int i = 0; i < numbers.length; ++i) {
            System.err.println(i + ” : ” + numbers[i]);
        }
        System.err.println(“value: ” + value);
        int found = find(value, numbers, 0, numbers.length);
        System.err.print(“found at index: ” + found);
    }

    public static int find(int value, int[] numbers, int start, int end) {
        System.err.println(“finding”);
        System.err.println(“start: ” + start);
        System.err.println(“end: ” + end);
        if (start == end) {
            if (numbers[start] == value) {
                return start;
            } else {
                return -1;
            }
        }
        int size = end - start; // size is at least 1 thanks to above condition.
        int middle = start + size / 2; // rounds down; middle may == start.
        System.err.println(“middle: ” + middle);
        int middleValue = numbers[middle];
        System.err.println(“middleValue: ” + middleValue);
        if (middleValue == value) {
            return middle;
        } else if (middleValue < value) {
            // take the top range of the array.
            return find(value, numbers, middle + 1, end);
        } else {
            // take the bottom range of the array.
            return find(value, numbers, start, middle);
        }
    }
}

numbers:
0 : 0
1 : 1
2 : 3
3 : 5
4 : 7
5 : 8
6 : 9
7 : 20
8 : 45
9 : 100
10 : 876
11 : 1000
12 : 1001
value: 45
finding
start: 0
end: 13
middle: 6
middleValue: 9
finding
start: 7
end: 13
middle: 10
middleValue: 876
finding
start: 7
end: 10
middle: 8
middleValue: 45
found at index: 8