你好,游客 登录 注册 搜索
背景:
阅读新闻

二分查找及其变形

[日期:2016-01-14] 来源:Linux社区  作者:linuxbug [字体: ]

C语言中可以用bsearch()实现二分查找。同qsort()一样,bsearch()也包含在glibc库中,且同样要自定义比较函数。其原型如下:

void *bsearch(const void *key, const void *base,

                    size_t nmemb, size_t size,

                    int (*compar)(const void *, const void *));

key指向所要查找的元素,base指向进行查找的数组,nmemb为查找长度,一般为数组长度,size为每个元素所占的字节数,一般用sizeof(...)表示,compar指向比较函数,它定义比较的规则。需要注意的是,数据必须是经过预先排序的,而排序的规则要和compar所指向比较函数的规则相同。如果查找成功则返回数组中匹配元素的地址,反之则返回空。对于有多于一个的元素匹配成功的情况,bsearch()未定义返回哪一个。

bsearch实现(glibc)
从glibc的代码可以看到,bsearch的实现是很简洁的:

 
/* Perform a binary search for KEY in BASE which has NMEMB elements
  of SIZE bytes each.  The comparisons are done by (*COMPAR)().  */
void *
bsearch (const void *key, const void *base, size_t nmemb, size_t size,
          int (*compar) (const void *, const void *))
{
  size_t l, u, idx;
  const void *p;
  int comparison;

  l = 0;
  u = nmemb;
  while (l < u)
  {
      idx = (l + u) / 2;
      p = (void *) (((const char *) base) + (idx * size));
      comparison = (*compar) (key, p);
      if (comparison < 0)
          u = idx;
      else if (comparison > 0)
          l = idx + 1;
      else
          return (void *) p;
  }
 
  return NULL;
}
bsearch_less的实现
参考bsearch的实现,我们可以实现bsearch的变形,来找到不大于key的最接近的那个数:

 
void *
bsearch_less (const void *key, const void *base, size_t nmemb, size_t size,
    int (*compar) (const void *, const void *))
{
  int l, u, idx;
  const void *p;
  int comparison;

  l = 0;
  u = nmemb - 1;
  while (l <= u)
  {
      idx = (l + u) / 2;
      p = (void *) (((const char *) base) + (idx * size));
      comparison = (*compar) (key, p);
      if (comparison < 0)
        u = idx - 1;
      else if (comparison > 0)
        l = idx + 1;
      else
        return (idx == 0) ? NULL : (void *) (((const char *) p) - size);
  }

  return (u < 0) ? NULL : (void *) (((const char *) base) + (u * size));
}
bsearch_more的实现
参考bsearch的实现,我们可以实现bsearch的变形,来找到不小于key的最接近的那个数:

 
void *
bsearch_more(const void *key, const void *base, size_t nmemb, size_t size,
        int (*compar) (const void *, const void *))
{
  int l, u, idx;
  const void *p;
  int comparison;

  l = 0;
  u = nmemb - 1;
  while (l <= u)
  {
      idx = (l + u) / 2;
      p = (void *) (((const char *) base) + (idx * size));
      comparison = (*compar) (key, p);
      if (comparison < 0)
        u = idx - 1;
      else if (comparison > 0)
        l = idx + 1;
      else
        return (idx == u) ? NULL : (void *) (((const char *) p) + size);
  }

  return (l > nmemb - 1) ? NULL : (void *) (((const char *) base) + (l * size));
}
示例:

 
/* bsearch example */
#include <stdio.h>      /* printf */
#include <stdlib.h>    /* qsort, bsearch, NULL */

void *
bsearch_less (const void *key, const void *base, size_t nmemb, size_t size,
    int (*compar) (const void *, const void *))
{
  int l, u, idx;
  const void *p;
  int comparison;

  l = 0;
  u = nmemb - 1;
  while (l <= u)
  {
      idx = (l + u) / 2;
      p = (void *) (((const char *) base) + (idx * size));
      comparison = (*compar) (key, p);
      if (comparison < 0)
        u = idx - 1;
      else if (comparison > 0)
        l = idx + 1;
      else
        return (idx == 0) ? NULL : (void *) (((const char *) p) - size);
  }

  return (u < 0) ? NULL : (void *) (((const char *) base) + (u * size));
}

void *
bsearch_more(const void *key, const void *base, size_t nmemb, size_t size,
        int (*compar) (const void *, const void *))
{
  int l, u, idx;
  const void *p;
  int comparison;

  l = 0;
  u = nmemb - 1;
  while (l <= u)
  {
      idx = (l + u) / 2;
      p = (void *) (((const char *) base) + (idx * size));
      comparison = (*compar) (key, p);
      if (comparison < 0)
        u = idx - 1;
      else if (comparison > 0)
        l = idx + 1;
      else
        return (idx == u) ? NULL : (void *) (((const char *) p) + size);
  }

  return (l > nmemb - 1) ? NULL : (void *) (((const char *) base) + (l * size));
}


int compareints (const void * a, const void * b)
{
  return ( *(int*)a - *(int*)b );
}

//int values[] = { 50, 20, 60, 40, 10, 30 };
int values[] = { 50, 20, 60, 30, 10, 30 };

void test_bsearch_less(int key)
{
  int* pItem = (int*) bsearch_less (&key, values, 6, sizeof (int), compareints);
  if (pItem!=NULL)
    printf ("%d is nearest less than %d int the array.\n",*pItem, key);
  else
    printf ("no key is less than %d in the array.\n",key);
}

void test_bsearch(int key)
{
  int* pItem = (int*) bsearch (&key, values, 6, sizeof (int), compareints);
  if (pItem!=NULL)
    printf ("%d is in the array.\n",*pItem);
  else
    printf ("%d is not in the array.\n",key);

}

void test_bsearch_more(int key)
{
  int* pItem = (int*) bsearch_more(&key, values, 6, sizeof (int), compareints);
  if (pItem!=NULL)
    printf ("%d is nearest more than %d int the array.\n",*pItem, key);
  else
    printf ("no key is more than %d in the array.\n",key);
}

void print_values(int* base, size_t nmemb)
{
  printf("values: ");
  for (size_t i = 0; i < nmemb; ++i)
  {
    printf("%d ", *(base+i));
  }
  printf("\n");
}

int main(int argc, char** argv)
{
  if (argc < 2)
  {
    printf("usage: ./bsearch_example num\n");
    return -1;
  }

  int key = atoi(argv[1]);
  qsort (values, 6, sizeof (int), compareints);
 
  print_values(values,6); 

  test_bsearch(key);
  test_bsearch_less(key);
  test_bsearch_more(key);
  return 0;
}
运行结果:

[root@VM_174_171_CentOS algorithm]# ./bsearch_example 1

values: 10 20 30 30 50 60

1 is not in the array.

no key is less than 1 in the array.

10 is nearest more than 1 int the array.

[root@VM_174_171_centos algorithm]# ./bsearch_example 10

values: 10 20 30 30 50 60

10 is in the array.

no key is less than 10 in the array.

20 is nearest more than 10 int the array.

[root@VM_174_171_centos algorithm]# ./bsearch_example 30

values: 10 20 30 30 50 60

30 is in the array.

20 is nearest less than 30 int the array.

30 is nearest more than 30 int the array.

[root@VM_174_171_centos algorithm]# ./bsearch_example 55

values: 10 20 30 30 50 60

55 is not in the array.

50 is nearest less than 55 int the array.

60 is nearest more than 55 int the array.

[root@VM_174_171_centos algorithm]# ./bsearch_example 60

values: 10 20 30 30 50 60

60 is in the array.

50 is nearest less than 60 int the array.

no key is more than 60 in the array.

[root@VM_174_171_centos algorithm]# ./bsearch_example 61

values: 10 20 30 30 50 60

61 is not in the array.

60 is nearest less than 61 int the array.

no key is more than 61 in the array.

本文永久更新链接地址http://www.linuxidc.com/Linux/2016-01/127433.htm

linux
相关资讯       二分查找 
本文评论   查看全部评论 (0)
表情: 表情 姓名: 字数

       

评论声明
  • 尊重网上道德,遵守中华人民共和国的各项有关法律法规
  • 承担一切因您的行为而直接或间接导致的民事或刑事法律责任
  • 本站管理人员有权保留或删除其管辖留言中的任意内容
  • 本站有权在网站内转载或引用您的评论
  • 参与本评论即表明您已经阅读并接受上述条款