异想天开

What's the true meaning of light, Could you tell me why

二分搜索

日期:2015-07-28 15:50:18
  
最后更新日期:2015-07-28 15:55:07
二分搜索代码:
[code lang="cpp"]
//bsearch.c
int mybsearch(int *_v, int low, int high, int key){
int mid = (high + low)/2;

for (; (_v[mid] != key) && (low <= high); mid = (high + low)/2)
{
if (_v[mid] < key){
low = mid + 1;
} else {
high = mid -1;
}
}
if (_v[mid] == key){
return mid;
} else {
return -1;
}
}
[/code]

单元测试:
[code lang="cpp"]
//mytest.c
CTEST(bsearch,one_to_thousand){
const int MAX_LEN = 1000;
int a[MAX_LEN];
int i = 0,j = 0, r = 0, k = 0;
for (i = 0; i < MAX_LEN; ++i){
a[i] = i;
}

for (i = 0; i < MAX_LEN; ++i){
for (j = 0; j < MAX_LEN; ++j){
for (k = i; k < j; ++k){
r = mybsearch(a,i,j,a[k]);
ASSERT_TRUE(r == k);
r = mybsearch(a,i,j,-1);
ASSERT_TRUE(r == -1);
}
}
}
}
[/code]
编译:
[code lang="cpp"]
gcc -Wall main.c bsearch.c mytest.c -o test
[/code]
main.c为CTEST框架封装main函数的c文件,mytest为单元测试文件,bsearch为二分搜索实现文件