binary search

gistfile1.cs

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