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

Question

我找不到实现二进制搜索的任何方法。是因为我找不到它，还是因为它不存在？

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

Answer 1

还有就是bsearch()在同样的方法<stdlib.h>，如上市这里，这里和这里。

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

通常，您应该使用qsort()before bsearch()，因为在搜索之前，应先对数组进行排序（应以升序排列，并使用与所使用的相同标准排序compare）。此步骤是必需的，因为二进制搜索算法会测试搜索关键字是高于还是低于数组的中间元素，然后消除数组的一半，测试结果的中间，再消除一半，依此类推。如果您为比较函数定义了bsearch()两个参数相同的类型，则qsort()可以使用相同的比较函数。

该bsearch()函数返回指向与搜索键匹配的数组元素的指针。如果找不到匹配的元素，则bsearch()返回空指针。^[一种]

使用示例：

/* 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，这是一种（可能是肮脏的）解决方法：您可以遍历排序后的数组，并key使用compare传递给此方法的相同函数比较其元素，直到您发现元素比少/大key。