C++ bsearch() 函数

bsearch() 函数要求在数组中被搜索元素的左侧所有元素都比它小。

同样，所有比被搜索元素大的元素必须在数组中的右侧。如果数组按升序排序，则满足此要求。

bsearch() 函数原型

void* bsearch (const void* key, const void* base, size_t num, size_t size, int (*compare)(const void*,const void*));

该函数定义在 <cstdlib> 头文件中。

bsearch() 函数在数组 base 中搜索 key。所有小于 key 的元素必须在数组 base 中的它之前出现。同样，所有大于 key 的元素必须在 base 中的它之后出现。

为了执行搜索，bsearch() 函数会对 compare 指向的函数进行一系列调用，key 作为第一个参数，数组中的一个元素作为第二个参数。

bsearch() 参数

• key：要搜索的元素的指针
• base：数组第一个元素的指针
• num：数组中的元素数量
• size：数组中每个元素的字节大小
• compare：一个比较两个元素的函数指针。它返回
  • 如果第一个参数小于第二个，则返回负整数
  • 如果第一个参数大于第二个，则返回正整数
  • 如果两个参数相等，则返回零

key 作为第一个参数传递，数组中的一个元素作为第二个参数传递。比较函数的原型如下：

int compare(const void* a, const void* b);

bsearch() 返回值

bsearch() 函数返回：

• 找到的元素的指针。如果找到多个匹配元素，则未指定函数将返回哪个元素的地址作为结果。
• 如果未找到元素，则返回空指针。

示例 1：bsearch() 函数如何工作？

#include <iostream>
#include <cstdlib>
using namespace std;

int compare(const void* a, const void* b)
{
	const int* x = (int*) a;
	const int* y = (int*) b;
	return (*x - *y);
}

int main()
{
	const int num = 10;
	int arr[num] = {5,9,10,14,16,19,21,26,29,31};
	int key1 = 10;
	int *p1 = (int*)bsearch(&key1,arr,num,sizeof(int),compare);

	if(p1 == NULL)
		cout << key1 << " 未找到 " << endl;
	else
		cout << key1 << " 找到位置 " << (p1-arr) << endl;

	int key2 = 15;
	int *p2 = (int*)bsearch(&key2,arr,num,sizeof(int),compare);
	if(p2 == NULL)
		cout << key2 << " 未找到 " << endl;
	else
		cout << key2 << " 找到位置 " << (p2-arr) << endl;
	return 0;
}

当你运行程序时，输出将是：

10 找到位置 2
15 未找到

示例 2：当有多个匹配元素时，bsearch() 函数如何工作？

#include <iostream>
#include <cstdlib>
using namespace std;

int compare(const void* a, const void* b)
{
	const int* x = (int*) a;
	const int* y = (int*) b;
	return (*x - *y);
}

int main()
{
	const int num = 10;
	int arr[num] = {2,3,5,7,8,10,14,14,14,15};
	int key = 14;
	int *p = (int*)bsearch(&key,arr,num,sizeof(int),compare);

	if(p == NULL)
		cout << key << " 未找到 " << endl;
	else
		/* 14 在位置 6,7 和 8 出现 */
		cout << key << " 找到位置 " << (p-arr) << endl;

	return 0;
}

当

你运行程序时，可能的输出将是：

14 找到位置 7