折半查找又叫二分查找，要求查找表本身必须是有序的。查找算法复杂度为O(logn)。C标准库提供折半查找的库函数，声明如下
bsearch(const void *, const void *, size_t, size_t, int (__cdecl *)(const void *, const void *));
最后一个参数要求一个指向比较函数的指针。程序设计实践上写道，为bsearch提供一个key就这么费劲，写一个好的通用的排序程序也不容易，即使这样，使用bsearch而不是自己另外写仍然是个好主意。
多年的历史证明，程序员能把二分检索程序写正确也是很不容易的(Over the years, binary search has proven surprisingly hard for programmer to get right)。
于是自己用模板写一个折半查找函数，写好一个十几行的程序，也不是看上去那么简单的事情。
template<typename T>
int binarysearch(const T* tab, int ntab, const T& value)
{
int low = 0;
int high = ntab;
while(low <= high)
{
int mid = (low+high)/2;
if(value<tab[mid])
high = mid - 1;
else if (value>tab[mid])
low = mid + 1;
else
return mid;
}
return -1;
}测试程序
int main(int argc, char* argv[])
{
int a[] = {2, 4, 6, 7, 8, 9, 13};
int aa = sizeof(a);
int n = binarysearch(a, sizeof(a)/sizeof(a[0]), 4);
cout<<n<<endl;
return 0;
}
posted on 2008-01-01 17:59
小四 阅读(1050)
评论(0) 编辑 收藏 引用 所属分类:
算法与数据结构