二分查找算法(Binary Search)的实现 [No. 26]

用二分查找在已排序的数组中查看该数组是否含有一个特定的值是非常快速的，时间复杂度为O(lgn). 二分查找思想很简单，但是实现的时候会在边界条件上出现一些意想不到的问题。 现贴出自己写的程序，供大家参考。

第一个实现是基于迭代方式：

/// <summary>
/// implement Binary Search algorithm through iteration approach.
/// </summary>
/// <param name="array">a sorted array</param>
/// <param name="key">key value </param>
/// <returns>the position of the key in the array. If this key is not found, return -1</returns>
public int BinarySearchIteration(int[] array, int key)
{
    int begin = 0;
    int end = array.Length - 1;
    while (begin <= end)
    {
        int mid = begin + (end - begin) / 2;
        if (array[mid] > key)
        {
            end = mid - 1;
        }
        else if (array[mid] < key)
        {
            begin = mid + 1;
        }
        else
        {
            return mid;
        }
    }
    return -1;
}

下一个是基于递归方式实现：

/// <summary>
/// implement Binary Search algorithm through recursion approach.
/// </summary>
/// <param name="array">a sorted array</param>
/// <param name="begin">the search starting position</param>
/// <param name="end">the search finishing position</param>
/// <param name="key">the key value</param>
/// <returns>the position of the key in the array. If this key is not found, return -1</returns>
public int BinaraySearchRecursive(int[] array, int begin, int end, int key)
{
    if (begin <= end)
    {
        int mid = begin + (end - begin) / 2;
        if (array[mid] > key)
        {
            return BinaraySearchRecursive(array, begin, mid - 1, key);
        }
        else if (array[mid] < key)
        {
            return BinaraySearchRecursive(array, mid + 1, end, key);
        }
        else
        {
            return mid;
        }
    }
    else
    {
        return -1;
    }
}

这里应该注意两个地方：

一是对于mid 的值，应该用代码中的方式获得，不能通过 mid = (begin + end) /2 来取得，因为 begin + end 的值会有可能大于 int 的最大值。

二是要注意在 if 判断的时候用 <=, 没有必要用 <， 然后再去做判断，否则会多此一举，而且也让代码显得很难看。

参考文献：

1.http://www.zhuoda.org/weiking/67932.html

2.http://www.cppblog.com/converse/archive/2009/02/28/75190.html