C标准库中是否有二进制搜索方法?

有一个 bsearch() 同一方法 <stdlib.h> ,如列表所示 here 我是说, here 和 here .

这个 搜索() 函数使用二进制搜索算法来查找与大小大小的n个元素的排序数组中的密钥相匹配的元素。(类型大小在 <stdlib.h> 最后一个参数, compare ,给予 搜索() 指向函数的指针,该函数调用该函数以将搜索键与任何数组元素进行比较。此函数必须返回一个值,该值指示其第一个参数search key是否小于、等于或大于要测试的数组元素。

你一般应该使用 qsort() 之前 搜索() ,因为数组 应该 是 已排序 (应按升序排列,以相同的标准使用) 比较 )在搜索之前。这一步是必要的,因为二进制搜索算法测试搜索键是否高于或低于数组中的中间元素,然后消除一半数组,测试结果的中间,再次消除一半,等等。如果定义比较函数 搜索() 两个参数的类型相同,则 qsort() 可以使用相同的比较函数。

这个 搜索() 函数返回指向找到的与搜索键匹配的数组元素的指针。如果没有找到匹配的元素, 搜索() 返回空指针。 ^[a]

示例使用 :

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

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

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

int main ()
{
  int * pItem;
  int key = 40;
  qsort (values, 6, sizeof (int), compareints);
  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);
  return 0;
}

输出:

40个在阵列中。

回应以下评论 关于如何找到小于/大于 key ,这里是( 可能很脏 )解决方法:可以迭代排序数组并将其元素与 钥匙 使用相同的 比较 传递给此方法的函数,直到找到小于/大于 钥匙 是的。

C库有一个标准功能 bsearch ,宣布 <stdlib.h> ,为此目的:在根据给定比较函数按升序排序的条目表中查找匹配的条目。

以下是C标准中的规范:

7.22.5.1 B搜索 功能

简介

#include <stdlib.h>
void *bsearch(const void *key, const void *base,
              size_t nmemb, size_t size,
              int (*compar)(const void *, const void *));

描述

这个 B搜索 函数搜索数组 nmemb 对象,其初始元素由 base ,对于与指向的对象匹配的元素 key 是的。数组中每个元素的大小由 size 是的。

所指的比较函数 compar 用两个参数调用,这两个参数按顺序指向键对象和数组元素。如果将键对象分别视为小于、匹配或大于数组元素,则函数应返回小于、等于或大于零的整数。数组应按顺序包括:比较小于的所有元素、比较等于的所有元素和比较大于关键对象的所有元素。 ^308年)

退换商品

这个 B搜索 函数返回指向数组中匹配元素的指针,如果找不到匹配元素,则返回空指针。 如果两个元素比较为相等,则未指定匹配的元素。

---

_{308)在实践中,根据比较函数对整个数组进行排序。}

此功能有两个缺点:

• 如果表包含重复的匹配条目,则不指定将返回哪个条目,如上面最后一段所强调的。
• 如果不能在表中找到该项,则该函数不能用来定位插入该项的位置,它只返回一个空指针。

这里有一个简单的实现来修复第一个点(它被编码为总是返回与数组开头最近的匹配条目),并且可以被修改以解决第二个问题:

#include <stdlib.h>

void *bsearch(const void *key, const void *base,
              size_t nmemb, size_t size,
              int (*compar)(const void *, const void *))
{
    const unsigned char *p;
    size_t m;
    int r;

    while (nmemb > 0) {
        m = (nmemb - 1) >> 1;
        p = (const unsigned char *)base + m * size;
        if ((r = compar(key, p)) < 0) {
            nmemb = m;
        } else
        if (r > 0) {
            base = p + size;
            nmemb -= m + 1;
        } else
        if (m == 0) {
            return (void *)p;
        } else {
            /* continue search to return first matching entry */
            nmemb = m + 1;
        }
    }
    // if you want the insertion point, you can return p here
    return NULL;
}