《The C Programming Language》中的小瑕疵

最近打算好好从C语言基础学起，在网上找到本《The C Programming Language》第二版电子书，Dennis Ritchie & Brian Kernighan合著。

读到第三章时，讲到一个二分法的搜索函数，测试了一下原书代码，如下：

/* binsearch: find x in v[0] <= v[1] <= .. <= v[n-1] */
int binsearch(int x, int v[], int n)
{
    int low, high, mid;

    low = 0;
    high = n - 1;
    while (low <= high) {
        mid = (low+high)/2;
        if (x < v[mid])
            high = mid + 1;
        else if (x > v[mid])
            low = mid + 1;
        else /* found match */
            return mid;
    }
    return -1; /* no match */
}

随机给一个数组赋值，然后用冒泡算法给数组排序，再让这个binsearch函数给数组排序，发现有时候，当数组中没有要搜索的值时，即binsearch函数的第一个参数x值，数组中没有这个x值，函数会陷入死循环，到网上一搜，看到这么一篇文章[1]，里面讲了二分法的问题，也给了一些示例代码，这才看到，是binsearch的代码有点小问题，即high = mid + 1;这行代码，应该是high = mid - 1;

重新再修改好代码，以下是正确的binsearch算法。

/* binsearch: find x in v[0] <= v[1] <= .. <= v[n-1] */
int binsearch(int x, int v[], int n)
{
    int low, high, mid;

    low = 0;
    high = n - 1;
    while (low <= high) {
        mid = (low+high)/2;
        if (x < v[mid])
            high = mid - 1;
        else if (x > v[mid])
            low = mid + 1;
        else /* found match */
            return mid;
    }
    return -1; /* no match */
}

一切都正常了。

参考文章:
[1]二分法——查找、排序以及库函数bsearch的用法
http://blog.csdn.net/douzixinxin/archive/2006/02/21/604144.aspx