バイナリサーチの実装

バイナリサーチアルゴリズムは大きな数値配列を素早く検索します。分割統治法としてよく知られています。

public class BinarySearch
{
    public int BinarySearch(int[] items, int searchValue)
    {
        int left = 0;
        int right = items.Length - 1;

        while (left <= right)
        {
            var middle = (left + right) / 2;

            //If the searchValue is in the center, we found it!
            if(items[middle] == searchValue)
            {
                return middle;
            }            

            //If the searchValue is less than the current middle, we set the right to (middle - 1)
            //Because the searchValue is in the lower half of the items.
            if(searchValue < items[middle])
            {
                right = middle - 1;    
            }
            //If the searchValue is greater than the current middle, we set the right to (middle + 1)
            //Because the searchValue is in the higher half of the items.
            else
            {
                left = middle + 1;
            }

        } // now that we've either found the item and returned it or we've reset our search boundaries
          // we'll search it again.

        // Not found.
        return -1;
    }
}