免费注册 查看新帖 |

Chinaunix

  平台 论坛 博客 文库
12下一页
最近访问板块 发新帖
查看: 7807 | 回复: 16

[算法] 二分查找的通用实现 [复制链接]

论坛徽章:
0
发表于 2013-09-29 10:12 |显示全部楼层
本帖最后由 术士 于 2013-09-29 10:13 编辑

如果你是愤青,请不要理会,只是为了传递下代码,现在的CU要提前声明,防止某些人乱喷
  1. /*============================================================================*/
  2. /*  Function : Search_Binary                                                  */
  3. /*  Input    : %1 -- Pointer Array Which Point To The Data Array              */
  4. /*             %2 -- Data To Search                                           */
  5. /*             %3 -- Data Array Length                                        */
  6. /*             %4 -- Compare Function Call Back                               */
  7. /*  Output   :                                                                */
  8. /*  Return   : The Index Of Array                                             */
  9. /*  Desc     : less the frst element, return 1                                */
  10. /*             more than the last element return arraylen - 1                 */
  11. /*             equal the element return index of element in array             */
  12. /*             more than the index element and less than the index + 1 element*/
  13. /*                                      return index + 1                      */
  14. /*  Author   :                                                              */
  15. /*  Version  : V1.00                                                          */
  16. /*  Date     : 2013.9.16                                                      */
  17. /*============================================================================*/
  18. /*  Modify Log:Must Have Date Author Description                              */
  19. /*  1.                                                                        */
  20. /*============================================================================*/
  21. UINT32 Search_Binary(void *pArray[], void *pItem, UINT32 ArrayLen, Compare fp)
  22. {
  23.     UINT32 High, Low, Mid;

  24.     High = ArrayLen - 1;
  25.     Low = 0;
  26.     Mid = (High + Low) / 2;

  27.     if (COMPARE_MORE == fp(pArray[0], pItem))
  28.     {
  29.         return 1;
  30.     }

  31.     if (COMPARE_LESS == fp(pArray[ArrayLen - 1], pItem))
  32.     {
  33.         return ArrayLen - 1;
  34.     }
  35.    
  36.     while (Low <= High)
  37.     {
  38.         if (COMPARE_MORE == fp(pArray[Mid], pItem))
  39.         {
  40.             High = Mid;
  41.             Mid = (High + Low) / 2;
  42.         }
  43.         else if (COMPARE_LESS == fp(pArray[Mid], pItem))
  44.         {
  45.             Low = Mid;
  46.             Mid = (High + Low) / 2;
  47.         }
  48.         else
  49.         {
  50.             return Mid;
  51.         }

  52.         if (COMPARE_MORE == fp(pArray[Mid + 1], pItem)
  53.             && COMPARE_LESS == fp(pArray[Mid], pItem))
  54.         {
  55.             return Mid + 1;
  56.         }
  57.     }
  58. }

  59. typedef unsigned int    UINT32;
  60. typedef UINT32 (* Compare)(void *, void *);
  61. #define COMPARE_EQUAL  0
  62. #define COMPARE_MORE   1
  63. #define COMPARE_LESS   2
复制代码

论坛徽章:
324
射手座
日期:2013-08-23 12:04:38射手座
日期:2013-08-23 16:18:12未羊
日期:2013-08-30 14:33:15水瓶座
日期:2013-09-02 16:44:31摩羯座
日期:2013-09-25 09:33:52双子座
日期:2013-09-26 12:21:10金牛座
日期:2013-10-14 09:08:49申猴
日期:2013-10-16 13:09:43子鼠
日期:2013-10-17 23:23:19射手座
日期:2013-10-18 13:00:27金牛座
日期:2013-10-18 15:47:57午马
日期:2013-10-18 21:43:38
发表于 2013-09-29 10:17 |显示全部楼层
我不说实现,我只是想问问LZ知道 bsearch 这个函数么?

论坛徽章:
7
摩羯座
日期:2013-12-05 10:42:57辰龙
日期:2013-12-27 13:40:49亥猪
日期:2014-01-15 09:10:37天秤座
日期:2014-01-20 11:22:20辰龙
日期:2014-01-26 17:02:25午马
日期:2014-01-27 14:22:34水瓶座
日期:2014-02-19 09:36:40
发表于 2013-09-29 10:18 |显示全部楼层
我觉得用模板实现更好

论坛徽章:
7
摩羯座
日期:2013-12-05 10:42:57辰龙
日期:2013-12-27 13:40:49亥猪
日期:2014-01-15 09:10:37天秤座
日期:2014-01-20 11:22:20辰龙
日期:2014-01-26 17:02:25午马
日期:2014-01-27 14:22:34水瓶座
日期:2014-02-19 09:36:40
发表于 2013-09-29 10:21 |显示全部楼层
没有办法,现在面试c/c++的经常让去实现快速排序等一系列的算法。


回复 2# hellioncu


   

论坛徽章:
15
射手座
日期:2014-11-29 19:22:4915-16赛季CBA联赛之青岛
日期:2017-11-17 13:20:09黑曼巴
日期:2017-07-13 19:13:4715-16赛季CBA联赛之四川
日期:2017-02-07 21:08:572015年亚冠纪念徽章
日期:2015-11-06 12:31:58每日论坛发贴之星
日期:2015-08-04 06:20:00程序设计版块每日发帖之星
日期:2015-08-04 06:20:00程序设计版块每日发帖之星
日期:2015-07-12 22:20:002015亚冠之浦和红钻
日期:2015-07-08 10:10:132015亚冠之大阪钢巴
日期:2015-06-29 11:21:122015亚冠之广州恒大
日期:2015-05-22 21:55:412015年亚洲杯之伊朗
日期:2015-04-10 16:28:25
发表于 2013-09-29 11:28 |显示全部楼层
hellioncu 发表于 2013-09-29 10:17
我不说实现,我只是想问问LZ知道 bsearch 这个函数么?

就是。系统已经提供,何必自己费心。除非你有特殊需求。

论坛徽章:
4
水瓶座
日期:2013-09-06 12:27:30摩羯座
日期:2013-09-28 14:07:46处女座
日期:2013-10-24 14:25:01酉鸡
日期:2014-04-07 11:54:15
发表于 2013-09-29 13:18 |显示全部楼层
我操, 这水准都出来抖擞? 真不能怪我们喷你, 自我感觉太良好了.

C都没学会的节奏吧,

  1. SYNOPSIS
  2.        #include <stdlib.h>

  3.        void *bsearch(const void *key, const void *base, size_t nmemb,
  4.               size_t size, int (*compar)(const void *, const void *));
复制代码
C++更别提了:
  1. std::binary_search
  2. default (1)       

  3. template <class ForwardIterator, class T>
  4.   bool binary_search (ForwardIterator first, ForwardIterator last,
  5.                       const T& val);

  6. custom (2)       

  7. template <class ForwardIterator, class T, class Compare>
  8.   bool binary_search (ForwardIterator first, ForwardIterator last,
  9.                       const T& val, Compare comp);
复制代码

论坛徽章:
15
射手座
日期:2014-11-29 19:22:4915-16赛季CBA联赛之青岛
日期:2017-11-17 13:20:09黑曼巴
日期:2017-07-13 19:13:4715-16赛季CBA联赛之四川
日期:2017-02-07 21:08:572015年亚冠纪念徽章
日期:2015-11-06 12:31:58每日论坛发贴之星
日期:2015-08-04 06:20:00程序设计版块每日发帖之星
日期:2015-08-04 06:20:00程序设计版块每日发帖之星
日期:2015-07-12 22:20:002015亚冠之浦和红钻
日期:2015-07-08 10:10:132015亚冠之大阪钢巴
日期:2015-06-29 11:21:122015亚冠之广州恒大
日期:2015-05-22 21:55:412015年亚洲杯之伊朗
日期:2015-04-10 16:28:25
发表于 2013-09-30 10:11 |显示全部楼层
本帖最后由 yulihua49 于 2013-09-30 10:14 编辑
linux_c_py_php 发表于 2013-09-29 13:18
我操, 这水准都出来抖擞? 真不能怪我们喷你, 自我感觉太良好了.

C都没学会的节奏吧,C++更别提了:

我倒是觉得如果能提供一些系统未能提供的功能,也行。可惜没看到。

例如:
bsearch_GT()
bsearch_GTEQ()
bserch_LT()
bserch_LTEQ()
up_bound()
low_bound()
等等。
linux_c_py_php 发表于 2013-09-29 13:18
我操, 这水准都出来抖擞? 真不能怪我们喷你, 自我感觉太良好了.

C都没学会的节奏吧,C++更别提了:

我倒是觉得如果能提供一些系统未能提供的功能,也行。可惜没看到。

例如:
bsearch_GT()
bsearch_GTEQ()
bserch_LT()
bserch_LTEQ()
up_bound()
low_bound()
等等。

论坛徽章:
0
发表于 2013-09-30 10:48 |显示全部楼层
难道没有人知道系统无关这句话的含义吗?好多情况下都要自己实现系统的很多函数啊。有人辛苦贴出来已经很不错了,凭什么去说别人啊。不想去提网上那些没有经过验证的代码了。

论坛徽章:
0
发表于 2013-09-30 17:21 |显示全部楼层
此贴可以有,谁没菜鸟过

论坛徽章:
36
子鼠
日期:2013-08-28 22:23:29黄金圣斗士
日期:2015-12-01 11:37:51程序设计版块每日发帖之星
日期:2015-12-14 06:20:00CU十四周年纪念徽章
日期:2015-12-22 16:50:40IT运维版块每日发帖之星
日期:2016-01-25 06:20:0015-16赛季CBA联赛之深圳
日期:2016-01-27 10:31:172016猴年福章徽章
日期:2016-02-18 15:30:3415-16赛季CBA联赛之福建
日期:2016-04-07 11:25:2215-16赛季CBA联赛之青岛
日期:2016-04-29 18:02:5915-16赛季CBA联赛之北控
日期:2016-06-20 17:38:50技术图书徽章
日期:2016-07-19 13:54:03程序设计版块每日发帖之星
日期:2016-08-21 06:20:00
发表于 2013-09-30 17:50 |显示全部楼层
楼主都说了借贵宝地,还是被喷了啊,哎,楼主慢走,支持楼主
您需要登录后才可以回帖 登录 | 注册

本版积分规则 发表回复

  

北京盛拓优讯信息技术有限公司. 版权所有 京ICP备16024965号-6 北京市公安局海淀分局网监中心备案编号:11010802020122 niuxiaotong@pcpop.com 17352615567
未成年举报专区
中国互联网协会会员  联系我们:huangweiwei@itpub.net
感谢所有关心和支持过ChinaUnix的朋友们 转载本站内容请注明原作者名及出处

清除 Cookies - ChinaUnix - Archiver - WAP - TOP