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 之前。同样，所有大于 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 << " not found " << endl;
	else
		cout << key1 << " found at position " << (p1-arr) << endl;

	int key2 = 15;
	int *p2 = (int*)bsearch(&key2,arr,num,sizeof(int),compare);
	if(p2 == NULL)
		cout << key2 << " not found " << endl;
	else
		cout << key2 << " found at position " << (p2-arr) << endl;
	return 0;
}

运行程序后，输出将是

10 found at position 2
15 not found

示例 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 << " not found " << endl;
	else
		/* 14 occurs at position 6,7 and 8*/
		cout << key << " found at position " << (p-arr) << endl;

	return 0;
}

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

14 found at position 7