BinarySearch

BinarySearch.java

public class BinarySearch {

    private BinarySearch() {
    }

    public static void main(String[] args) {
        Integer[] data = {1,2,3,4,5,6,7,8,9};
        for (int i=0; i<=10; ++i) {
            System.out.println(String.format("%d: %d", i, binarySearch(data, i)));
        }
    }

    public static <T extends Comparable<T>> int binarySearch(final T[] data, final T key) {
        int l = -1;
        int u = data.length;
        // pre condition:
        // data[l] < key <= data[u], l < u + 1
        while (l + 1 != u) {
            int m = l + (u - l)/2;
            if (data[m].compareTo(key) < 0) {
                l = m;
            } else {
                u = m;
            }
        }
        // post condition:
        // data[l] < key <= data[u], l <= u + 1
        int result = u;
        if (result == data.length || data[result].compareTo(key) != 0) {
            result = -result-1;
        }
        return result;
    }
}