二分查找算法（迭代和递归版本）

二分查找算法（迭代和递归版本）2010-05-16 C++博客那谁Bentley在他的著作《Writing Correct Programs》中写道，90%的计算机专家不能在2小时内写出完全正确的二分搜索算法。

我自己尝试了一下,确实要第一次就完全写正确不容易.以下两份实现依次为迭代和递归版本的代码,二分查找的思想很多人都清楚,但是这里有一个细节就是要注意边界的选择.

int search（int array[],int n,int v）
{
    int left,right,middle;

    left = 0,right = n - 1;

    while （left <= right）
    {
        middle = （left + right） / 2;
        if （array[middle] > v）
        {
            right = middle - 1;
        }
        else if （array[middle] < v）
        {
            left = middle + 1;
        }
        else
        {
            return middle;
        }
    }

    return -1;
}

int search_recurse（int array[],int low,int high,int v）
{
    int middle;

    middle = （low + high） / 2;

    if （low < high）
    {
        if （array[middle] > v）
        {
            return search_recurse（array,low,middle,v）;
        }
        else if （array[middle] < v）
        {
            return search_recurse（array,middle + 1,high,v）;
        }
        else
        {
            return middle;
        }
    }
    else if （low == high）
    {
        if （array[middle] == v）
        {
            return middle;
        }
        else
        {
            return -1;
        }

    }
    else
    {
        return -1;
    }

    return -1;
}

int main（）
{
    int array[] = {0,1,2,3,4,5,6,7,13,19};

    int m = search（array,sizeof（array）/sizeof（array[0]）,13）;

    printf（"m = %d
",m）;

    m = search_recurse（array,0,sizeof（array）/sizeof（array[0]）,13）;

    printf（"m = %d
",m）;

    return 0;
}