二分法总结

二分法是常用的查找有序数组中元素位置的算法，其基本的查找时间效率为O(lgn)。本文总结二分法的递归查找算法和非递归查找算法。
二分法的非递归的算法代码如下：

int search(int array[], int len, int target)
{
    int low, high, middle;

    low = 0, high = len - 1;

    while(low <= high)
    {
        middle = (int)((low +  high) >> 1);
        if(array[middle] < target)
        {
               low = middle +  1;
        }
        else if(array[middle] > target)
        {
               high = middle - 1;
        }
        else
        {
               return middle;
        }
    }

    return -1;
}

二分法的递归算法代码如下：

int search_recursive(int array[], int low, int high, int target)
{
    int middle = (int)((low + high) >> 1);

    if(low <= high)
    {
        if(array[middle] < target)
        {
            return search_recursive(array, middle + 1, high, target);
        }
        else if(array[middle] > target)
        {
               return search_recursive(array, low, middle - 1, target);
        }
        else
        {
               return middle;
        }
    }

    return -1;
}

上述代码有可能有一些特殊情况问题，但大体应该是正确的，这里先不管了。
二分法的返回值为查找变量的出现的位置，上述代码虽然能够返回变量出现的位置，但是却不是该变量在有序数组中出现的第一个位置。为了让二分查找返回变量出现在有序数组中的第一个位置，如下述代码所示（其实这也是二分法的优化，感谢willgo）。

int search(int array[], int len, int target)
{
    int low, high, middle;

    low = -1, high = len;

    while(low + 1 != high)
    {
        middle = (int)((low + high) >> 1);
        if(array[middle] < target)
        {
               low = middle;
        }
        else
        {
            high = middle;
        }
    }
    if(high == len || array[high] != target)
    {
        return -1;
    }

    return high;
}