c - C 标准库中有二进制搜索方法吗？

Question

我找不到任何实现二分查找的方法。是我没找到，还是根本不存在？

_{我认为是第二个，但我找不到重复的问题，所以也许我错了。}

Answer 1

有bsearch()相同的方法 <stdlib.h> , 如所列 here , here和 here .

bsearch()函数使用二进制搜索算法在大小为 size 的 n 个元素的排序数组中查找与键匹配的元素。 (类型 size_t 在 <stdlib.h> 中定义为无符号整数。)最后一个参数 compare , 给出 bsearch()指向函数的指针，调用该函数以将搜索键与任何数组元素进行比较。此函数必须返回一个值，该值指示其第一个参数(搜索键)是否小于、等于或大于其第二个参数(要测试的数组元素)。

您通常应该使用 qsort()之前bsearch() ，因为数组应该在搜索之前被排序(应该按升序排列，按照 compare 使用的相同标准排序)。这一步是必要的，因为二分搜索算法会测试搜索关键字是否高于或低于数组中的中间元素，然后消除数组的一半，测试结果的中间，再次消除一半，等等。如果为 bsearch() 定义比较函数两个参数的类型相同，然后是 qsort()可以使用相同的比较函数。

bsearch()函数返回指向找到的与搜索键匹配的数组元素的指针。如果没有找到匹配的元素，bsearch()返回空指针。 ^[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 is in the array.

回应下面关于如何找到小于/大于 key 的第一个元素的评论 ，这是一个(可能很脏)解决方法:您可以迭代排序数组并将其元素与 key 进行比较使用相同的 compare传递给此方法的函数，直到找到小于/大于 key 的元素.