C语言数组的二进制搜索
下面的程序提供了两种搜索方法,第一种较为直观,但是效率低。
before=[1403854047,472312], after=[1403854048,176352]
The difference is 704040
-----------------------------------------------------------------------------------
before= [1403854048,176352], after=[1403854048, 747385]
The difference is 571033
注意:<sys/time.h> 是Linux中的头文件,以上程序在 VC6.0 中编译不能通过,笔者在 MinGW 5 下编译通过。
笔者顺便推荐一款国产C语言开发神器 -- C-Free 5.0 -- 默认编译器是 MinGW,详情请查看:C-Free 5.0下载[带注册码][赠送破解版][最性感的C、C++开发工具IDE]
#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; }输出结果:
before=[1403854047,472312], after=[1403854048,176352]
The difference is 704040
-----------------------------------------------------------------------------------
before= [1403854048,176352], after=[1403854048, 747385]
The difference is 571033
注意:<sys/time.h> 是Linux中的头文件,以上程序在 VC6.0 中编译不能通过,笔者在 MinGW 5 下编译通过。
笔者顺便推荐一款国产C语言开发神器 -- C-Free 5.0 -- 默认编译器是 MinGW,详情请查看:C-Free 5.0下载[带注册码][赠送破解版][最性感的C、C++开发工具IDE]