/**
 * Binary search for integer arrays.
 *
 * @author Stefan Nilsson, snilsson@nada.kth.se
 * @version 09-01-20
 */
public class BinarySearch {
    public static final int NOT_FOUND = -1;

    /**
     * Returns index of the first occurence of key in the sorted
     * array v, or -1 if key is not found.
     * <p>
     * If the array isn't sorted the behavior is undefined.
     * <p>
     * Time complexity: O(log n), where n = v.length.
     */
    public int binSearch(int[] v, int key) {
	if (v.length > 0)
	    return binSearch(v, 0, v.length - 1, key);
	else
	    return NOT_FOUND;
    }

    /**
     * Returns index of the first occurence of key in the sorted
     * subarray v[first..last], or -1 if key is not found.
     * Precondition: first <= last.
     */
    private int binSearch(int[] v, int first, int last, int key) {
	if (first == last) {
	    return key == v[first] ? first : NOT_FOUND;
	}

	// subarray with more than one element
	int mid = first + (last - first)/2;
	if (key <= v[mid]) {
	    return binSearch(v, first, mid, key);
	} else {
	    return binSearch(v, mid + 1, last, key);
	}
    }

    /**
     * Unit test. Run with <code>java -ea BinarySearch</code>.
     */
    public static void main(String[] args) {
	BinarySearch bs = new BinarySearch();

	int[] v0 = {};
	assert bs.binSearch(v0, 0) == NOT_FOUND;

	int[] v1 = {1};
	assert bs.binSearch(v1, 0) == NOT_FOUND;
	assert bs.binSearch(v1, 1) == 0;
	assert bs.binSearch(v1, 2) == NOT_FOUND;

	int[] v2a = {1, 3};
	assert bs.binSearch(v2a, 0) == NOT_FOUND;
	assert bs.binSearch(v2a, 1) == 0;
	assert bs.binSearch(v2a, 2) == NOT_FOUND;
	assert bs.binSearch(v2a, 3) == 1;
	assert bs.binSearch(v2a, 4) == NOT_FOUND;

	int[] v2b = {1, 1};
	assert bs.binSearch(v2b, 0) == NOT_FOUND;
	assert bs.binSearch(v2b, 1) == 0;
	assert bs.binSearch(v2b, 2) == NOT_FOUND;

	int[] v3a = {1, 3, 5};
	assert bs.binSearch(v3a, 0) == NOT_FOUND;
	assert bs.binSearch(v3a, 1) == 0;
	assert bs.binSearch(v3a, 2) == NOT_FOUND;
	assert bs.binSearch(v3a, 3) == 1;
	assert bs.binSearch(v3a, 4) == NOT_FOUND;
	assert bs.binSearch(v3a, 5) == 2;
	assert bs.binSearch(v3a, 6) == NOT_FOUND;

	int[] v3b = {1, 1, 3};
	assert bs.binSearch(v3b, 0) == NOT_FOUND;
	assert bs.binSearch(v3b, 1) == 0;
	assert bs.binSearch(v3b, 2) == NOT_FOUND;
	assert bs.binSearch(v3b, 3) == 2;
	assert bs.binSearch(v3b, 4) == NOT_FOUND;

	int[] v3c = {1, 3, 3};
	assert bs.binSearch(v3c, 0) == NOT_FOUND;
	assert bs.binSearch(v3c, 1) == 0;
	assert bs.binSearch(v3c, 2) == NOT_FOUND;
	assert bs.binSearch(v3c, 3) == 1;
	assert bs.binSearch(v3c, 4) == NOT_FOUND;

	int[] v3d = {1, 1, 1};
	assert bs.binSearch(v3d, 0) == NOT_FOUND;
	assert bs.binSearch(v3d, 1) == 0;
	assert bs.binSearch(v3d, 2) == NOT_FOUND;

	int min = Integer.MIN_VALUE;
	int max = Integer.MAX_VALUE;
	int[] v = {min, min, -1, -1, 0, 1, 1, max, max, max};
	assert bs.binSearch(v, min) == 0;
	assert bs.binSearch(v, -1) == 2;
	assert bs.binSearch(v, 0) == 4;
	assert bs.binSearch(v, 1) == 5;
	assert bs.binSearch(v, max) == 7;
	assert bs.binSearch(v, -1000) == NOT_FOUND;
	assert bs.binSearch(v, 1000) == NOT_FOUND;
    }
}