二分查找C代码实现

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

/*
 * file: test.c
 * author: [e-mail]
 * history:
 * initial @ 2012-02-29
 */

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

#include "bin_search.h"


static int __comp(const int *key, const int *dst)
{
  if(*key < *dst)
    return -1;
  else if (*key > *dst)
    return 1;
  else
    return 0;
}

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

static void __dump(int *arrp, size_t cnts)
{
  int i;
  for (i=0; i<cnts; i++)
    printf("%d ", arrp[i]);
  printf("\n");
}

#define __msg_out(key, pmatched) {               \
    if (pmatched) \
      printf("key:%d matched with address %p\n", key, pmatched);  \
    else\
      printf("key:%d nothing match any one of the array!\n", key);\
    }                                                             \

#define test_out(arr,cnts,key) { \
    __dump((arr), (cnts));       \
    int *pmatched=0;                                                    \
    pmatched = bin_search((arr), (cnts), sizeof(arr[0]), &key, __comp); \
    __msg_out(key, pmatched);                                           \
}

int main(void)
{
  int *pmatched=0;
  int i, key;
  int arr0[] = {1};
  int arr1[] = {1,4};
  int arr2[] = {1,4,8};
  int arr3[] = {1,4,8,10};
  int arr4[] = {1,4,8,10,18};
  int arr5[] = {1,4,8,10,18,23};
  int arr6[] = {1,4,8,10,18,23,26};

  for (key=0; key <= 28; key++)
  {
    printf ("--------------0--------------\n");
    test_out(arr0, ARRAY_SIZE(arr0), key)
    printf ("--------------1--------------\n");
    test_out(arr1, ARRAY_SIZE(arr1), key)
    printf ("--------------2--------------\n");
    test_out(arr2, ARRAY_SIZE(arr2), key)
    printf ("--------------3--------------\n");
    test_out(arr3, ARRAY_SIZE(arr3), key)
    printf ("--------------4--------------\n");
    test_out(arr4, ARRAY_SIZE(arr4), key)
    printf ("--------------5--------------\n");
    test_out(arr5, ARRAY_SIZE(arr5), key)
    printf ("--------------6--------------\n");
    test_out(arr6, ARRAY_SIZE(arr6), key)
  }
  return 0;
}

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

/*
 * file: bin_search.h
 * author: [e-mail]
 * history:
 * initial @ 2012-02-29
 */
#ifndef __BIN_SEARCH_H_
#define __BIN_SEARCH_H_

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

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

#endif

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

/*
 * file: bin_search.c
 * author: [e-mail]
 * history:
 * initial @ 2012-02-29
 */

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

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

void * bin_search(const void* arrp, size_t cnts, size_t size, void *key, compf __cmp)
{
  int min=0, max=cnts-1, mid;
  __assert( arrp && key && pos1<=pos2);
  while(min <= max)
  {
    mid = (min+max+1)>>1;
    if (__cmp(key, __pdata(arrp,mid,size)) < 0)
      /* smaller than the key, search from min to mid position */
      max = mid-1;
    else if (__cmp(key, __pdata(arrp,mid,size)) > 0)
      /* bigger than the key, search from mid to max position */
      min = mid+1;
    else
      /* match the key, return the address of the data */
      return __pdata(arrp,mid,size);
  }
  return 0;
}

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

#Makefile

CC := gcc

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

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

附件：
 bin_search.rar