这篇“C语言折半查找法如何使用”文章的知识点大部分人都不太理解,所以小编给大家总结了以下内容,内容详细,步骤清晰,具有一定的借鉴价值,希望大家阅读完这篇文章能有所收获,下面我们一起来看看这篇“C语言折半查找法如何使用”文章吧。
折半查找也称二分查找,是一种在有序数组中查找某一特定元素的搜索算法,每一次查找,搜索范围均缩小一半,效率较高。如果数组是乱序状态,则应排序,再进行查找。
搜索过程从数组的中间元素开始,如果中间元素正好是要查找的元素,则搜索过程结束;如果某一特定元素大于或者小于中间元素,则在数组大于或小于中间元素的那一半中查找,而且跟开始一样从中间元素开始比较。如果在某一步骤数组为空,则代表找不到。这种搜索算法每一次比较都使搜索范围缩小一半 。
总共有n个元素,每次查找的区间大小就是n,n/2,n/4,…,n/ 2 k 2^k 2k,一直到1,其中k就是循环的次数。
由于n/ 2 k 2 ^ k 2k取整后>=1,即令n/ 2 k 2^k 2k=1,可得k=log2n,(是以2为底,n的对数),所以时间复杂度可以表示O()=O(logn)。
二分查找只需要额外存储三个变量:最大值 ,最小值 和 中点,空间复杂度为常数 O(1)。
优点:比较次数少,查找速度快,平均性能好。
缺点:要求待查表为有序表,且插入删除困难。
输入需要查找的元素,我们输入的是38;left是有序数组最左端0,是最小值,right是有序数组最右端10,是最大值,mid为数组1/2位置,即array[5];
38比array[5] = 19大,因此left等于原mid+1,即array[6] = 26,right不变;新mid为(left+right)/2 = (6+10)/2 = 8;
38比array[8] = 36大,因此left等于上一次mid+1,即array[9] = 38,right不变;新mid为(left+right)/2 = (9+10)/2 = 9;
38等于array[9],mid与left重合, 查找成功,返回数组下标9.
#include <stdio.h> #include <string.h> int binarySearch(int array[],int len,int target){ int left = 0; int right = len - 1; while(left <= right){ int mid = (right + left) / 2; if(array[mid] == target){ return mid; } else if(array[mid] < target){ left = mid + 1; } else if(array[mid] > target){ right = mid - 1; } } return -1; } int main(void) { int array[]={2,3,4,5,15,19,26,27,36,38,45}; int key = 0,ret; printf("请输入需要查找的数字:"); scanf("%d",&key); ret = binarySearch(array,sizeof(array)/sizeof(int),key); if(ret < 0) printf("查找失败\n"); else printf("该数字为数组第%d个元素\n",ret+1); return 0; }
运行结果:
请输入需要查找的数字:38
该数字为数组第10个元素
以上就是关于“C语言折半查找法如何使用”这篇文章的内容,相信大家都有了一定的了解,希望小编分享的内容对大家有帮助,若想了解更多相关的知识内容,请关注亿速云行业资讯频道。
免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。