二分搜索

看《编程珠玑》，里面介绍了一些二分搜索，在这里记录一下。

本文只包含四种二分搜索实现：普通的，返回第一次出现位置，返回最后一次出现位置，递归的。 书中还有一个对二分搜索进行加速的例子，但这里就不记录了，毕竟二分搜索已经很快了。

二分搜索是一种查找算法，对给定的序列中查找指定的键值。要求序列是排好序了的。这里序列不一定是数字，可以是其他任何你排序后的事物。

牢记：“虽然第一篇二分搜索论文在1946年就发表了，但是第一个没有错误的二分搜索程序却直到1962年才出现”

（1）普通的

int int_bsearch(int a[], int n, int key)
{  /* 在数组a中查找key，a应该已排序 */
    int l, h;
    int mid;

    l = 0;
    h = n - 1;

    while(l <= h)
    {
        mid = (l + h) / 2;
        if(a[mid] > key)
            h = mid - 1;
        else if(a[mid] == key)
            return mid;           /* found match */
        else
            l = mid + 1;
    }
    return -1;                    /* cannot found match */
}

（2）递归的

int recu_bsearch(int a[], int n, int key)
{
    int mid;

    if(n <= 0)
        return -1;
    mid = (n - 1) / 2;
    if(a[mid] == key)
        return mid;
    else if(a[mid] > key)
        return recu_bsearch(a, mid, key);
    else
        return mid + 1 + recu_bsearch(&a[mid+1], n-mid-1, key);
}

（3）返回第一次出现位置的

即返回key在数组a中第一次出现的位置。 看代码后就能知道，该方法要比“普通的”方法要快那么一点，因为减少了一次比较操作

int first_bsearch(int *a, int n, int key)
{
    int low, high;
    int mid;
    int pos;

    /* assume a[low] < key and a[high] >= key */
    low = -1;
    high = n;
    while(low+1 != high)
    {
        mid = (low + high) / 2;
        if(a[mid] < key)
        {
            low = mid;
        }
        else
            high = mid;
    }
    pos = high;                 /* found */
    if(pos == n || a[pos] != key)
        pos = -1;               /* not found match */
    return pos;
}

（4）返回最后一次出现的

即返回key在数组a中最后一次出现的位置。

int lastpos(int *a, int n, int key)
{
    int l, u, m;

    l = -1;
    u = n;

    /* assume x[l] <= t < x[u] */
    while(u - 1 != l)
    {
        m = (l + u) / 2;
        if(a[m] > key)
            u = m;
        else
            l = m;
    }

    if(l == -1 || x[l] != key)
        return -1;
    return l;
}

由于“牢记”里的那句话，所以我有点不敢确定这些代码都是100%正确，若发现问题，还望告知，万分感谢！