bsearch的用法

bsearch(二分法查找)

原型:

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

基本定义:

在有序表中，取中间记录作为比较对象，若给定值与中间记录的值相等，则查找成功；若给定值小于中间记录的值，则在中间记录的左半区继续查找；若给定值大于中间记录的值，则在中间记录的右半区继续查找。不断重复上述过程，直到找到为止。

限制条件:

在查找需要对列表进行sort，使列表变为有序状态。

Parameters

测试代码

#include <iostream>
#include <algorithm>
#include <cstdlib>

using namespace std;

int compare(const void *ap, const void *bp)
{
	const int *a = (int *)ap;
	const int *b = (int *)bp;
	if (*a < *b)
		return -1;
	else if (*a > *b)
		return 1;
	else
		return 0;
}

int main(int argc, char **argv)
{
	const int ARR_SIZE = 8;
	int arr[ARR_SIZE] = { 1, 2, 3, 4, 5, 6, 7, 8 };

	int key1 = 4;
	int *p1 = (int *)std::bsearch(&key1, arr, ARR_SIZE, sizeof(arr[0]), compare);
	if (p1)
		std::cout << "value " << key1 << " found at position " << (p1 - arr) << '\n';
	else
		std::cout << "value " << key1 << " not found\n";

	int key2 = 9;
	int *p2 = (int *)std::bsearch(&key2, arr, ARR_SIZE, sizeof(arr[0]), compare);
	if (p2)
		std::cout << "value " << key2 << " found at position " << (p2 - arr) << '\n';
	else
		std::cout << "value " << key2 << " not found\n";

	system("pause");
	return 0;
}