c语言查找算法: 二分查找个人笔记

二分查找的原理

二分查找法实质上是不断地将有序数据集进行对半分割，并检查每个分区的中间元素。再重

复根据中间数确定目标范围并递归实行对半分割，直到中间数等于待查找的值或是目标数不在搜

索范围之内！

二分查找的代码实现

二分查找的问题

使用二分查找在一个序数组中查找一个数,有则返回这个数在数组中的下标,没有则返回-1;

源代码

使用循环实现

#include 
   
    using namespace std;/****************************************函数作用: 比较int类型的数**函数参数: left -  左边的数据(在这里是需要查询的数据)*		   right - 右边的数据(在这里是指定数组中的数)**函数返回值: *left - *right int类型的相减结果*************************************/int int_compare(const void* left, const void* right) {	const int* key1 = (const int*)left;	const int* key2 = (const int*)right; 	return (*key1 - *key2);}/****************************************函数作用: 比较char类型的数据**函数参数: left -  左边的数据(在这里是需要查询的数据)*		   right - 右边的数据(在这里是指定数组中的数)**函数返回值:  *left - *right char类型的相减结果*************************************/char char_compare(const void* left, const void* right) {	const char* key1 = (const char*)left;	const char* key2 = (const char*)right;	return (*key1 - *key2);}/****************************************函数作用: 二分查找数据int 类型的数据**函数参数: arr - 任何类型的有序数组首地址*          len - arr数组的长度*          elementSize - arr数组中一个元素占的内存*          search - 任何类型的数据(需要在arr数组中查找的数据)*          函数指针  - int_compare int 类型的比较函数*                      char_compare char 类型的函数指针*          如果比较char类型的数据 把函数指针改了就行**函数返回值: arr数组中if have search data return 在arr数组中的下标 else return -1;*************************************/int binarySearch(void* arr, int len, int elementSize, void* search, int (*int_compare)(const void* key1,const void* key2)) {	int left = 0; //arr数组开始遍历的下标 0	int right = len - 1; //arr数组最后的下标 len-1;    int middle = 0; 	int ret = -1;	//在left 至 right 区间遍历	while (left <= right) {		middle = (right + left) / 2; //相较于left 和 right中间的数据				//因为arr是void*类型 不知道arr占几个字节 强制转换成char *		//char*就一个字节  middle*elementSize 就 == arr[middle]		ret = (*int_compare)(search, (char*)arr + (middle*elementSize));		//ret== 0 *search == arr[middle] ;		if (ret == 0) {			//返回middle数组下标			return middle;		}		//ret< 0; arr[middle] 大于 *search ;		else if (ret < 0) {			//开始遍历middle左边的数据 直到ret == 0;			right = middle - 1;		}		//ret > 0; arr[middle] 小于 *search;		else {			//开始遍历middle右边的数据 直到 ret == 0;			left = middle + 1;		}	}	return -1;}int main(void) {	//有序数组	int arr[] = { 1,3,7,9,11 };	//测试用例search数组中的数据都是需要查询的数据	int search[] = {0,1,2,3,4,7,8,9,11,13};		//arrlen 是 arr 数组中的长度	int arrlen = sizeof(arr) / sizeof(arr[0]);	int index = -2;	for (int i = 0; i < sizeof(search) / sizeof(search[0]); i++) {		  //&int_compare 是int_compare 函数的地址		index = binarySearch(arr, arrlen, sizeof(int), &search[i], &int_compare);		printf("searchNumber is %d ,the searchNumnber in the arr index: %d\n", search[i], index);	}	char arr1[] = { 'a','b','c','e', 'f'};	char search1[] = { 'c','d','b','e','j','z','x','f' };	int arrlen1 = sizeof(arr1) / sizeof(arr1[0]);	/*for (int i = 0; i < sizeof(search1) / sizeof(search1[0]); i++) {		index = binarySearch(arr1, arrlen1, sizeof(char), &search1[i], &char_compare);		printf("searchNumber is %c ,the searchNumnber in  arr index: %d\n", search1[i], index);	}*/	return 0;}