二分查找的通用实现

术士

如果你是愤青，请不要理会，只是为了传递下代码，现在的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. 
    
25.     High = ArrayLen - 1;
    
26.     Low = 0;
    
27.     Mid = (High + Low) / 2;
    
28. 
    
29.     if (COMPARE_MORE == fp(pArray[0], pItem))
    
30.     {
    
31.         return 1;
    
32.     }
    
33. 
    
34.     if (COMPARE_LESS == fp(pArray[ArrayLen - 1], pItem))
    
35.     {
    
36.         return ArrayLen - 1;
    
37.     }
    
38.    
    
39.     while (Low <= High)
    
40.     {
    
41.         if (COMPARE_MORE == fp(pArray[Mid], pItem))
    
42.         {
    
43.             High = Mid;
    
44.             Mid = (High + Low) / 2;
    
45.         }
    
46.         else if (COMPARE_LESS == fp(pArray[Mid], pItem))
    
47.         {
    
48.             Low = Mid;
    
49.             Mid = (High + Low) / 2;
    
50.         }
    
51.         else
    
52.         {
    
53.             return Mid;
    
54.         }
    
55. 
    
56.         if (COMPARE_MORE == fp(pArray[Mid + 1], pItem)
    
57.             && COMPARE_LESS == fp(pArray[Mid], pItem))
    
58.         {
    
59.             return Mid + 1;
    
60.         }
    
61.     }
    
62. }
    
63. 
    
64. typedef unsigned int    UINT32;
    
65. typedef UINT32 (* Compare)(void *, void *);
    
66. #define COMPARE_EQUAL  0
    
67. #define COMPARE_MORE   1
    
68. #define COMPARE_LESS   2

复制代码

hellioncu

我不说实现，我只是想问问LZ知道 bsearch 这个函数么？

kdkgod

我觉得用模板实现更好

kdkgod

没有办法，现在面试c/c++的经常让去实现快速排序等一系列的算法。


回复 2# hellioncu


   

yulihua49

hellioncu 发表于 2013-09-29 10:17
我不说实现，我只是想问问LZ知道 bsearch 这个函数么？

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

linux_c_py_php

我操, 这水准都出来抖擞? 真不能怪我们喷你, 自我感觉太良好了.

C都没学会的节奏吧,

1. 
   
2. SYNOPSIS
   
3.        #include <stdlib.h>
   
4. 
   
5.        void *bsearch(const void *key, const void *base, size_t nmemb,
   
6.               size_t size, int (*compar)(const void *, const void *));

复制代码

C++更别提了:

1. std::binary_search
   
2. default (1)       
   
3. 
   
4. template <class ForwardIterator, class T>
   
5.   bool binary_search (ForwardIterator first, ForwardIterator last,
   
6.                       const T& val);
   
7. 
   
8. custom (2)       
   
9. 
   
10. template <class ForwardIterator, class T, class Compare>
    
11.   bool binary_search (ForwardIterator first, ForwardIterator last,
    
12.                       const T& val, Compare comp);

复制代码

yulihua49

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()
等等。

shilihua

难道没有人知道系统无关这句话的含义吗？好多情况下都要自己实现系统的很多函数啊。有人辛苦贴出来已经很不错了，凭什么去说别人啊。不想去提网上那些没有经过验证的代码了。

eveson

此贴可以有，谁没菜鸟过

cokeboL

楼主都说了借贵宝地，还是被喷了啊，哎，楼主慢走，支持楼主