九天雁翎的博客
如果你想在软件业获得成功,就使用你知道的最强大的语言,用它解决你知道的最难的问题,并且等待竞争对手的经理做出自甘平庸的选择。 -- Paul Graham

一天一个C Run-Time Library 函数 (11) bsearch

 

一天一个C Run-Time Library 函数  (11)  bsearch

write by 九天雁翎(JTianLing) -- www.jtianling.com

 

msdn:

Performs a binary search of a sorted array. A
more secure version is available; see
bsearch_s.

void
*bsearch(

   const void *key,

   const void *base,

   size_t num,

   size_t width,

   int ( __cdecl *compare ) ( const void *, const
void *)

);

 

 

测试程序:(来自MSDN)

#include <search.h>

#include <string.h>

#include <stdio.h>

 

int compare( char **arg1, char **arg2 )

{

    /* Compare all of both strings: */

    return _strcmpi(
*arg1, *arg2
);

}

 

int main( void )

{

    char *arr[]
= {"dog", "pig",
"horse", "cat",
"human", "rat",
"cow", "goat"};

    char **result;

    char *key
= "cat";

    int i;

 

    /* Sort using Quicksort algorithm: */

    qsort( (void *)arr, sizeof(arr)/sizeof(arr[0]), sizeof( char * ), (int (*)(const

       void*, const void*))compare );

 

    for( i
= 0; i < sizeof(arr)/sizeof(arr[0]); ++i
)    /* Output
sorted list */

       printf( "%s ", arr[i] );

 

    /* Find the word "cat" using
a binary search algorithm: */

    result = (char **)bsearch( (char *) &key,
(char *)arr,
sizeof(arr)/sizeof(arr[0]),

       sizeof( char * ), (int (*)(const void*, const void*))compare );

    if( result
)

       printf( "/n%s found at %Fp/n", *result, result
);

    else

       printf( "/nCat not found!/n" );

}

说明:

bsearch又是一个看起来相当有用,但是其实我却一次都没有在实际工作中碰到需要用的函数。。。。二分查找是算法教学的经典内容,呵呵

实际中我还真没有碰到这样的需要,因为碰到需要快速查找的时候一般都用map搞定了。。。人哪。。。才发现用C++也是会越来越懒的。。。。。因为有STL吗,所以map用的不亦乐乎,早完了C语言中该怎么来实现类似效果了。其实就算是想要实现我也很可能是用C++算法库的binary_search吧。

 

 

实现:

MS:

gcc:

对于这样经典的算法好像gccMS终于没有办法不一致了,事实上也是如此,两者几乎没有任何区别,其实现可以在任何关于算法的书籍上找到。

 

效率测试:

见以前有人说过C++的二分查找会比C语言的快,这是很多用C++的人证明C++不比C语言慢的一个例证。但是实际上,我也一直认为,不用其他非C语言特性的东西,为啥C++会比C语言慢呢?除非硬是碰到喜欢用类来描述这样算法的人吧。

 

相关函数:

qsort,不先排序,二分查找可是没有办法进行的

 

个人想法:

非常标准的C语言函数,通用性非常好。最后,我越来越懒了,并且发现这样写下去已经比较脱离我当时的想法了。。。。。现在每天工作回来还真的是很辛苦,脑袋都一直比较痛的感觉。。。。呵呵,郁闷啊。另外,再一次证明了我的恒心和毅力都是很有问题的。于是我找到了又一个来拖延此专题的借口,那就是我发现我现在去学习关于数据结构和算法还有Unix环境高级编程等书的话,实际意义更大。。。。。。。另外,对于多弄弄lua,python也是很有益处,没有想到C语言函数库的函数这么多,这么杂,这么多我完全就没有用过。。。。。用C++的人(比如我),常常将自己使用的语言称为C/C++,似乎表示自己用C++,就一直象在用C一样,自己懂C++也就懂C,不过,其实两者的区别,比我想的要大的多.因为C++有了太多特性,所以很多C语言的相关特性难免都被丢在了被遗忘的角落了.

 

 

write by 九天雁翎(JTianLing) -- www.jtianling.com

 

分类:  C++ 
标签:  bsearch  C++ 

Posted By 九天雁翎 at 九天雁翎的博客 on 2008年11月19日

分享到:

前一篇: 一个无聊男人的疯狂《数据结构与算法分析-C++描述》学习笔记 用C++/lua/python/bash的四重实现(2) IntCell类 后一篇: 为学习APUE(Unix环境高级编程)偷懒,而写的脚本,基本上相当于一个简单的工程创建脚本了