BinarySearcher.cs

usingSystem;
usingSystem.Collections;
usingSystem.Collections.Generic;
usingAlgorithms.Sorting;

namespaceAlgorithms.Search
{
publicclassBinarySearcher<T>:IEnumerator<T>
{
privatereadonlyIList<T>_collection;
privatereadonlyComparer<T>_comparer;
privateT_item;
privateint_currentItemIndex;
privateint_leftIndex;
privateint_rightIndex;

/// <summary>
/// The value of the current item
/// </summary>
publicTCurrent
{
get
{
return_collection[_currentItemIndex];
}
}

objectIEnumerator.Current=>Current;

/// <summary>
/// Class constructor
/// </summary>
/// <param name="collection">A list</param>
/// <param name="comparer">A comparer</param>
publicBinarySearcher(IList<T>collection,Comparer<T>comparer)
{
if(collection==null)
{
thrownewNullReferenceException("List is null");
}
_collection=collection;
_comparer=comparer;
HeapSorter.HeapSort(_collection);
}

/// <summary>
/// Apply Binary Search in a list.
/// </summary>
/// <param name="item">The item we search</param>
/// <returns>If item found, its' index, -1 otherwise</returns>
publicintBinarySearch(Titem)
{
boolnotFound=true;

if(item==null)
{
thrownewNullReferenceException("Item to search for is not set");
}
Reset();
_item=item;

while((_leftIndex<=_rightIndex)&&notFound)
{
notFound=MoveNext();
}

if(notFound)
{
Reset();
}
return_currentItemIndex;
}

/// <summary>
/// An implementation of IEnumerator's MoveNext method.
/// </summary>
/// <returns>true if iteration can proceed to the next item, false otherwise</returns>
publicboolMoveNext()
{
_currentItemIndex=this._leftIndex+(this._rightIndex-this._leftIndex)/2;

if(_comparer.Compare(_item,Current)<0)
{
_rightIndex=_currentItemIndex-1;
}
elseif(_comparer.Compare(_item,Current)>0)
{
_leftIndex=_currentItemIndex+1;
}
else
{
returnfalse;
}
returntrue;
}

publicvoidReset()
{
this._currentItemIndex=-1;
_leftIndex=0;
_rightIndex=_collection.Count-1;
}

publicvoidDispose()
{
//not implementing this, since there are no managed resources to release 
}
}
}