import java.util.Arrays;

/**
 * Binary search for integer arrays.
 *
 * @author Stefan Nilsson, snilsson@nada.kth.se
 * @version 10-01-16
 */
public class BS {
	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 static 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 static 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);
		}
	}

	private static class TestCase {
		int[] v;
		int key;
		int res;
	}

	// TestCase builder
	private static TestCase tc(int[] v, int key, int res) {
		TestCase t = new TestCase();
		t.v = v;
		t.key = key;
		t.res = res;
		return t;
	}

	// int[] builder
	private static int[] ia(int... v) {
		return v;
	}

	/**
	 * Unit test.
	 */
	public static void main(String[] args) {
		int min = Integer.MIN_VALUE;
		int max = Integer.MAX_VALUE;
		int[] v10 = {min, min, -1, -1, 0, 1, 1, max, max, max};

		TestCase[] tests = new TestCase[] {		
			tc(v10, min, 0),
			tc(v10, -1, 2),
			tc(v10, 0, 4),
			tc(v10, 1, 5),
			tc(v10, max, 7),
			tc(v10, -1000, -1),
			tc(v10, 1000, -1),

			tc(ia(), 0, -1),

			tc(ia(1), 0, -1),
			tc(ia(1), 1, 0),
			tc(ia(1), 2, -1),

			tc(ia(1, 3), 0, -1),
			tc(ia(1, 3), 1, 0),
			tc(ia(1, 3), 2, -1),
			tc(ia(1, 3), 3, 1),
			tc(ia(1, 3), 4, -1),

			tc(ia(1, 1), 0, -1),
			tc(ia(1, 1), 1, 0),
			tc(ia(1, 1), 2, -1),

			tc(ia(1, 3, 5), 0, -1),
			tc(ia(1, 3, 5), 1, 0),
			tc(ia(1, 3, 5), 2, -1),
			tc(ia(1, 3, 5), 3, 1),
			tc(ia(1, 3, 5), 4, -1),
			tc(ia(1, 3, 5), 5, 2),
			tc(ia(1, 3, 5), 6, -1),

			tc(ia(1, 1, 3), 0, -1),
			tc(ia(1, 1, 3), 1, 0),
			tc(ia(1, 1, 3), 2, -1),
			tc(ia(1, 1, 3), 3, 2),
			tc(ia(1, 1, 3), 4, -1),

			tc(ia(1, 3, 3), 0, -1),
			tc(ia(1, 3, 3), 1, 0),
			tc(ia(1, 3, 3), 2, -1),
			tc(ia(1, 3, 3), 3, 1),
			tc(ia(1, 3, 3), 4, -1),

			tc(ia(1, 1, 1), 0, -1),
			tc(ia(1, 1, 1), 1, 0),
			tc(ia(1, 1, 1), 2, -1),
		};

		for (TestCase x: tests) {
			int[] v = x.v;
			int key = x.key;
			int res = binSearch(v, key);

			if (res != x.res) {
				System.err.println("binSearch(" + Arrays.toString(v) + ", "
					+ key + ") = " + res + "; want " + x.res);
			}
		}
	}
}