Chinaunix首页 | 论坛 | 博客
  • 博客访问: 676779
  • 博文数量: 122
  • 博客积分: 3923
  • 博客等级: 中校
  • 技术积分: 1382
  • 用 户 组: 普通用户
  • 注册时间: 2009-04-23 01:22
文章分类

全部博文(122)

文章存档

2013年(1)

2012年(21)

2011年(70)

2009年(30)

分类: LINUX

2012-02-29 18:12:07

今天实现了一下二分查找,不过数组必须有序。。。

  1. /*
  2.  * file: test.c
  3.  * author: vincent.cws2008@gmail.com
  4.  * history:
  5.  * initial @ 2012-02-29
  6.  */

  7. #include <stdio.h>
  8. #include <stdlib.h>

  9. #include "bin_search.h"


  10. static int __comp(const int *key, const int *dst)
  11. {
  12.   if(*key < *dst)
  13.     return -1;
  14.   else if (*key > *dst)
  15.     return 1;
  16.   else
  17.     return 0;
  18. }

  19. #define ARRAY_SIZE(arr) (sizeof(arr)/sizeof(arr[0]))

  20. static void __dump(int *arrp, size_t cnts)
  21. {
  22.   int i;
  23.   for (i=0; i<cnts; i++)
  24.     printf("%d ", arrp[i]);
  25.   printf("\n");
  26. }

  27. #define __msg_out(key, pmatched) { \
  28.     if (pmatched) \
  29.       printf("key:%d matched with address %p\n", key, pmatched); \
  30.     else\
  31.       printf("key:%d nothing match any one of the array!\n", key);\
  32.     } \
  33.     
  34. #define test_out(arr,cnts,key) { \
  35.     __dump((arr), (cnts)); \
  36.     int *pmatched=0; \
  37.     pmatched = bin_search((arr), (cnts), sizeof(arr[0]), &key, __comp); \
  38.     __msg_out(key, pmatched); \
  39. }
  40.     
  41. int main(void)
  42. {
  43.   int *pmatched=0;
  44.   int i, key;
  45.   int arr0[] = {1};
  46.   int arr1[] = {1,4};
  47.   int arr2[] = {1,4,8};
  48.   int arr3[] = {1,4,8,10};
  49.   int arr4[] = {1,4,8,10,18};
  50.   int arr5[] = {1,4,8,10,18,23};
  51.   int arr6[] = {1,4,8,10,18,23,26};
  52.   
  53.   for (key=0; key <= 28; key++)
  54.   {
  55.     printf ("--------------0--------------\n");
  56.     test_out(arr0, ARRAY_SIZE(arr0), key)
  57.     printf ("--------------1--------------\n");
  58.     test_out(arr1, ARRAY_SIZE(arr1), key)
  59.     printf ("--------------2--------------\n");
  60.     test_out(arr2, ARRAY_SIZE(arr2), key)
  61.     printf ("--------------3--------------\n");
  62.     test_out(arr3, ARRAY_SIZE(arr3), key)
  63.     printf ("--------------4--------------\n");
  64.     test_out(arr4, ARRAY_SIZE(arr4), key)
  65.     printf ("--------------5--------------\n");
  66.     test_out(arr5, ARRAY_SIZE(arr5), key)
  67.     printf ("--------------6--------------\n");
  68.     test_out(arr6, ARRAY_SIZE(arr6), key)
  69.   }
  70.   return 0;
  71. }
--------------------------------------------------------------------------------------------

  1. /*
  2.  * file: bin_search.h
  3.  * author: vincent.cws2008@gmail.com
  4.  * history:
  5.  * initial @ 2012-02-29
  6.  */
  7. #ifndef __BIN_SEARCH_H_
  8. #define __BIN_SEARCH_H_

  9. typedef int (*compf)(const void *key, const void *dst);

  10. void *bin_search(const void* arrp, size_t cnts, size_t size, void *key, compf __cmp);

  11. #endif

--------------------------------------------------------------------------------------------
  1. /*
  2.  * file: bin_search.c
  3.  * author: vincent.cws2008@gmail.com
  4.  * history:
  5.  * initial @ 2012-02-29
  6.  */

  7. #include <stdlib.h>
  8. #include "bin_search.h"

  9. #define __assert(x)
  10. #define __pdata(arrp,pos,size) (((char*)arrp)+(size)*(pos))

  11. void * bin_search(const void* arrp, size_t cnts, size_t size, void *key, compf __cmp)
  12. {
  13.   int min=0, max=cnts-1, mid;
  14.   __assert( arrp && key && pos1<=pos2);
  15.   while(min <= max)
  16.   {
  17.     mid = (min+max+1)>>1;
  18.     if (__cmp(key, __pdata(arrp,mid,size)) < 0)
  19.       /* smaller than the key, search from min to mid position */
  20.       max = mid-1;
  21.     else if (__cmp(key, __pdata(arrp,mid,size)) > 0)
  22.       /* bigger than the key, search from mid to max position */
  23.       min = mid+1;
  24.     else
  25.       /* match the key, return the address of the data */
  26.       return __pdata(arrp,mid,size);
  27.   }
  28.   return 0;
  29. }

--------------------------------------------------------------------------------------------

  1. #Makefile

  2. CC := gcc

  3. default: test.o
  4.     $(CC) -lm bin_search.c test.c -o test

--------------------------------------------------------------------------------------------

附件:
 bin_search.rar  
阅读(3941) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~
评论热议
请登录后评论。

登录 注册