binary search

gistfile1.java

/**
 * Function returns location of unique item in a sorted list.
 * 
 * @param <T> Class, that implements comparable interface.
 * @param data list of elements
 * @param searchValue element to search for
 * @return Location of the the element. If item is not found, -1 is returned.
 * @throws java.lang.NullPointerException
 *             If any checked element in the list is 'null'.
 */
public static <T extends Comparable<? super T>> //
int binarySearch(final List<T> data, T searchValue)
		throws java.lang.NullPointerException {
	return binarySearch(data, searchValue, 0, data.size() - 1);
}

/**
 * Function returns location of unique item in a sorted list.
 * 
 * @param <T> Class, that implements comparable interface.
 * @param data list of elements
 * @param searchValue element to search for
 * @param left lower bound
 * @param right upper bound
 * @return Location of the the element. If item is not found, -1 is returned.
 * @throws java.lang.NullPointerException
 *             If any checked element in the list is 'null'.
 */
public static <T extends Comparable<? super T>> //
int binarySearch(final List<T> data, T searchValue, int left, int right)
		throws java.lang.NullPointerException {
	final int NOT_FOUND = -1;
	if (right < left)
		return NOT_FOUND;

	int mid = (left + right) >>> 1;
	int cmp = searchValue.compareTo(data.get(mid));
	if (cmp > 0)
		return binarySearch(data, searchValue, mid + 1, right);
	if (cmp < 0)
		return binarySearch(data, searchValue, left, mid - 1);
	return mid;
}