集团门户网站建设公司,电商培训机构有哪些哪家比较好,网站建设要准备什么软件,公司网站开发有哪些写程序的时候#xff0c;肯定避免不了需要从集合中找到符合条件的元素#xff0c;一般情况下#xff0c;最简单也最常用的就是循环遍历元素#xff0c;这种方法虽然写的简单#xff0c;但是小数据量还行#xff0c;但是数据过大的话#xff0c;这样效率就低了。循环的时…写程序的时候肯定避免不了需要从集合中找到符合条件的元素一般情况下最简单也最常用的就是循环遍历元素这种方法虽然写的简单但是小数据量还行但是数据过大的话这样效率就低了。循环的时候比如你要的数据正好在集合的最后那就需要把前面的每一个元素都要对比一次如果你要查找的数据正好在前几个那就很快找到到了。但数据这东西毕竟不是可控的。
所以要查找我们就要采用一点技巧和方法在C/C中搜索的时候可以使用bsearch函数来实现元素的查找这个函数定义在头文件stdlib.h中使用方式如下
本文所有代码在 cygwin,gcc 11.3,gdb 11.2 中编译调试
bsearch的基本使用方法
bsearch函数的使用方法简单,函数定义如下
void* bsearch( const void *key, const void *ptr, size_t count, size_t size,int (*comp)(const void*, const void*) );具体参数如下
key - 指向要查找的元素的指针
ptr - 指向要检验的数组的指针
count - 数组的元素数目
size - 数组每个元素的字节数
comp - 比较函数。若首个参数小于第二个则返回负整数值若首个参数大于第二个则返回正整数值若两参数等价则返回零。 将 key 传给首个参数数组中的元素传给第二个。 comp函数的定义如下
int cmp(const void *a, const void *b);cmp参数说明a表示要查找的那个元素b表示查找数组里的元素
举例如下从数组f中查找x,如果找到就打印“找到11”没找到就打印没找到11
#include stdio.h
#include stdlib.h
const int x 11;
const int f[] { 1,3,6,9,11 };
int cmp(const void *a, const void *b) {int x1 (int)(*(int*)a);int x2 (int)(*(int*)b);printf(x1:%d\n, x1);printf(x2:%d\n, x2);if (x1 x2) return -1;else if (x1 x2) return 1;else return 0;
}
int main(int, char**) {int* c (int*)bsearch(x, f, 5, sizeof (int), cmp);if( c ! NULL ) {printf(找到%d\n,x);}else {printf(没找到%d\n,x);}return 1;
}输出如下
x1:11
x2:6
x1:11
x2:11
找到 11可以看到通过bsearch函数从f中找到了11
但是观察cmp函数中的两行printf代码
printf(x1:%d\n, x1);
printf(x2:%d\n, x2);它表示打印要查找的元素也就是上例的x,x2表示被查找的f中的某个元素通过观察输出的结果可以发现虽然f数组中有{ 1,3,6,9,11 }5个元素但实际上比较函数并没有比较全部元素只比较的两次就找到了11.
这就是文章开头说到的循环遍历会降低效率而使用bsearch会让查找速度加快应为bsearch的查找并非遍历元素而是采用了二分法查找,bsearch的第一个字幕b代表的就是Bisection/baɪˈsekʃən/中文意思为“二等分
关于二分法查找
在查找上使用二分法是通过多次切分被查找的数组然后和要查找的元素组做对比具体步骤如下
假设数组为arr,要查找的元素为key,数组长度为len,进行如下操作
1.把被查找的数组长度除以2得到的中间值mid,作为索引去数组中取值arr[mid]
2.使用比对函数进行对比第一步取到的arr[mid]和要查找的值key如果返回的值小于0也就说明要查找的值key在数组的索引为0到mid中间。然后,修改要查找的数组起始位置重复第一步在0到mid中间查找
如果返回的值大于0就说明要查找的值key在数组的索引为mid到数组的最后一个元素之间。然后修改要查找的数组起始位置重复第一步在arr[mid]到最后个元素中间查找
3.重复如上23步,然后最终找到你要找的值
4.如果返回返回0说明找到了可以返回了
例如
从[1,2,3,4,5]中找到4
5/2 2,先找到索引是2的3因为3比4小说明4在索引2以后(215)/2 4, 索引4就是5 比4大所以在所以在索引4以前,3以后(34)/2 3索引3就是4找到了
以上就是使用二分法的流程
自己实现一个bsearch
void * mybsearch(const void* base, int len, int size, const void* key, int (*cmp)(const void* a, const void* b))
{size_t low 0, high len;while (low high){int mid (low high) / 2;void * p (void *) (((const char *) base) (mid * size));int comret (*cmp) (key,p);if (comret 0)high mid;else if (comret 0)low mid 1;elsereturn p;}return NULL;
}然后还是刚才的代码
#include stdio.h
#include stdlib.h
const int x 11;
const int f[] { 1,3,6,9,11 };
int cmp(const void *a, const void *b) {int x1 (int)(*(int*)a);int x2 (int)(*(int*)b);printf(x1:%d\n, x1);printf(x2:%d\n, x2);if (x1 x2) return -1;else if (x1 x2) return 1;else return 0;
}
int main(int, char**) {int* c (int*)mybsearch(f,5, sizeof (int), x, cmp);if( c ! NULL ) {printf(找到%d\n,x);}else {printf(没找到%d\n,x);}return 1;
}执行一下看结果
x1:11
x2:6
x1:11
x2:11
找到 11运行结果正确
知道的二分法的原理就知道bsearch该如何使用什么情况下bsearch就找不到你要的元素
例如如果把要查找的数组和要查找的元素修改为
const int x 2;
const int f[] { 1,3,6,9,2 };的话bsearch就无法从f中找到2因为你的数组并不是单调的按照二分法的查找方式就找不到
所以使用bsearch时候如果不能确认数组是排序好的就要先调用qsort把数组排序好然后在使用查找 如上例经过qsort以后数据会排序好然后就能正常使用bsearch了
