二分法查找

写一个二分法查找的程序，也没有那么容易。我试验了一下，写了一个。

int* search(int a[], int len, int v)
{
    if(len <= 0) {
        return NULL;
    }
    int mid = len/2;
    int c = a[mid];
    if(c == v){
        return a + mid;
    }else if(c > v) {
        return search(a, mid, v);
    }else {
        return search(a + mid + 1, len - mid - 1, v);
    }
    return NULL;
}

验证程序如下：

int main(int argc, char *argv[])
{
    int a[] = { 5,6,10,18,19};
    int len = sizeof(a) / sizeof(int);
    int * p = NULL;
    int b[] = {4,5,6,7,9,10,19,20};
    int lenb = sizeof(b)/sizeof(int);
    for(int i = 0; i < lenb; ++i){
        p = search(a,len, b[i]);
        if(p!=NULL){
            int d = p - a;
            printf("found %d at a[%d]\n", b[i], d);
        }else {
            printf("%d not found\n", b[i]);
        }
    }
    return 0;
}

程序输出结果如下:

4 not found
found 5 at a[0]
found 6 at a[1]
7 not found
9 not found
found 10 at a[2]
found 19 at a[4]
20 not found

写程序的时候，我脑子里需要记住几个基本规则，自己不能违反这些规则。

数组的长度是 len
数组最后一个元素是 a[len-1]
len == 0 数组为空。
数组下标 a[mid]，那么 a[mid] 之前有 mid 个元素。不包含 a[mid]。
数组下标 a[mid]，那么 a[mid] 后面一个元素的是 a[mid+1]
数组下标 a[mid]，那么从 a[mid] 到数组结尾，一共有 len-mid 个元素。包含 a[mid] 。
特别的，当 mid = 0 的时候，从 a[0] 到数组结尾，一共有 len 个元素。包含 a[0]。
如果数组下标 a[mid+1] ，那么从 a[mid+1] 到数组结尾，一共有 len - mid - 1 个元素。即，不包含 a[mid] 的时候，一共有多少个元素。

这个程序有一个很有争议的风格问题。

if(c==v) {
    return a + mid
}

是否可以在程序中间返回？另一种风格是如下，

int* search(int a[], int len, int v)
{
    int * result = NULL;
    if(len <= 0) {
        result = NULL;
    }else {
        int mid = len/2;
        int c = a[mid];
        if(c == v){
            result = a + mid;
        }else if(c > v) {
            result = search(a, mid, v);
        }else {
            result = search(a + mid + 1, len - mid - 1, v);
        }
    }
    return result;
}

两种风格各有利弊，不做深聊了。

这个程序还有一个问题，就是尾递归。c 语言的尾递归是一种优化，不是语义上支持的。也就是说，当 len 非常非常大的时候，是否 stack overflow ，全凭 c 编译器优化开关的心情。如果我们不依赖于 c 的编译器的话，可以手工写尾递归的风格。

int* search(int a[], int len, int v)
{
    int * result = NULL;

TAIL_CALL:
    if(len <= 0) {
        result = NULL;
    }else {
        int mid = len/2;
        int c = a[mid];
        if(c == v){
            result = a + mid;
        }else if(c > v) {
            a = a;
            len = mid;
            v = v;
            goto TAIL_CALL;
        }else {
            a = a + mid + 1;
            len = len - mid - 1;
            v = v;
            goto TAIL_CALL;
        }
    }
    return result;
}

也就是说

result = search(<V1>, <V2>, <V3>);

被修改为:

a = <V1>
len = <V2>
c = <V3>
goto TAIL_CALL;

v=v 当然是没有必要的，这里为了强调是尾递归。

这种风格的尾递归，违反了大公司定义的风格。

不允许使用 goto；
不允许修改过输入参数；

这里面还有一个风格的问题。就是如何写 if 语句。

if 尽量带 else
if elseif else 风格的代码，最好覆盖所有的可能性。

讨论详见 2015-07-08-C_C++-编程风格:-if-else.html

Wang Chunye

二分法查找