C语言数组的二进制搜索

下面的程序提供了两种搜索方法，第一种较为直观，但是效率低。

#include <stdio.h>
#include <sys/time.h>
// 给定一个包含 n 个元素的数组 a，对 who 进行二进制搜索；成功返回 who 的位置，否则返回 -1
int binary1(int n, int a[n], int who) {
    int left = 0;
    int right = n-1;
    while (left <= right) {
        int mid = left + (right-left)/2;
    if (who < a[mid])
        right = mid - 1;
    else if (who > a[mid])
        left = mid + 1;
    else
        return mid;
    }
    return -1;
}
// 给定一个包含 n 个元素的数组 a，对 who 进行二进制搜索；成功返回 who 的位置，否则返回 -1
int binary2(int n, int a[n], int who) {
    int p = n/2;
    while (n > 0) {
        n = n/2;
        if (who < a[p]) {
            p -= n;
        } else if (who > a[p]) {
            p += n;
        } else
            return p;
    }
    return -1;
}
// 返回before 和 after 的差值（以微妙计算
long timediff(struct timeval before, struct timeval after) {
    long sec = after.tv_sec - before.tv_sec;
    long microsec = after.tv_usec - before.tv_usec;
    return 1000000*sec + microsec;
}
int main() {
    int a[] = {1,3,5,7,9,11,13,15,17,19,21,23,25,27,29,31,33};
    int n = sizeof(a)/sizeof(int);
    int where;
    struct timeval before;
    struct timeval after;
    int k;
    int j;
    gettimeofday(&before, NULL);
    for (j = 0; j < 1000000; j++)
        for (k = 0; k < 2*n+1; k++) {
            where = binary1(n, a, k);
            // printf("who = %d, \tvalue = %d\n", k, where);
        }
    gettimeofday(&after, NULL);
    printf("before=[%ld,%ld], after=[%ld,%ld]\n", before.tv_sec, before.tv_usec, after.tv_sec, after.tv_usec);
    printf("The difference is %ld\n", timediff(before, after));
    printf("---------------------------------------------\n");
    gettimeofday(&before, NULL);
    for (j = 0; j < 1000000; j++)
        for (k = 0; k < 2*n+1; k++) {
            where = binary2(n, a, k);
            // printf("who = %d, \tvalue = %d\n", k, where);
        }
    gettimeofday(&after, NULL);
    printf("before=[%ld,%ld], after=[%ld,%ld]\n", before.tv_sec, before.tv_usec, after.tv_sec, after.tv_usec);
    printf("The difference is %ld\n", timediff(before, after));
    return 0;
}

输出结果：

注意：<sys/time.h> 是Linux中的头文件，以上程序在 VC6.0 中编译不能通过，笔者在 MinGW 5 下编译通过。

笔者顺便推荐一款国产C语言开发神器 -- C-Free 5.0 -- 默认编译器是 MinGW，详情请查看：C-Free 5.0下载[带注册码][赠送破解版][最性感的C、C++开发工具IDE]