Binary search

Java
In java, Collections/Arrays class contains binary search.

view plainprint?

1. Collections.binarySearch(list, key);  
2. Arrays.binarySearch(array, key);  

Collections.binarySearch(list, key);
Arrays.binarySearch(array, key);

My naive generic implementation is recursive and ignores the fact, that I should use ListIterator for data structures, that do not have random access (ex. LinkedList).

	/**
	* 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;
	}

view raw gistfile1.java hosted with ❤ by GitHub

C#
In C#, list itself and Arrays class contains binary search.

list.BinarySearch(key);
Array.BinarySearch(array, key);

My naive Java implementation translated to C#.

	/// <summary>
	/// Function returns location of unique item in a sorted list.
	/// </summary>
	/// <typeparam name="T">Class, that implements comparable interface.</typeparam>
	/// <param name="data">list of elements</param>
	/// <param name="searchValue">element to search for</param>
	/// <returns>Location of the the element. If item is not found, -1 is returned.</returns>
	/// <exception cref="System.NullReferenceException">
	/// If any checked element in the list is 'null'. (Other then first one)
	/// </exception>
	public static int binarySearch<T>(IList<T> data, T searchValue)
	where T : IComparable<T>
	{
	return binarySearch(data, searchValue, 0, data.Count());
	}
	/// <summary>
	/// Function returns location of unique item in a sorted list.
	/// </summary>
	/// <typeparam name="T">Class, that implements comparable interface.</typeparam>
	/// <param name="data">list of elements</param>
	/// <param name="searchValue">element to search for</param>
	/// <param name="left">lower bound</param>
	/// <param name="right">upper bound</param>
	/// <returns>Location of the the element. If item is not found, -1 is returned.</returns>
	/// <exception cref="System.NullReferenceException">
	/// If any checked element in the list is 'null'. (Other then first one)
	/// </exception>
	public static int binarySearch<T>(IList<T> data, T searchValue, int left, int right)
	where T : IComparable<T>
	{
	const int NOT_FOUND = -1;
	if (right < left)
	return NOT_FOUND;
	int mid = (int)((uint)(left + right) >> 1);
	int cmp = searchValue.CompareTo(data[mid]);
	if (cmp > 0)
	return binarySearch(data, searchValue, mid + 1, right);
	if (cmp < 0)
	return binarySearch(data, searchValue, left, mid - 1);
	return mid;
	}

view raw gistfile1.cs hosted with ❤ by GitHub

Mathematica
In mathematica, Combinatorica library contains binary search.

BinarySearch[list, key]