C语言程序设计:二分查找(折半查找)
2021/12/15 1:16:39
本文主要是介绍C语言程序设计:二分查找(折半查找),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
文章目录
- C语言程序设计:二分查找(折半查找)
- 1.什么是二分查找
- 2.二分查找的优点
- 3.二分查找的缺点
- 4.二分查找原理
- 5.源代码实现
- 6.后话
C语言程序设计:二分查找(折半查找)
1.什么是二分查找
二班查找又称折半查找,他是一种高效率的查询方法。
2.二分查找的优点
高效,减少查询次数,查找的速度快,平均性能好(貌似 快速排序 也是),非递归实现(我觉得也是优点吧)。
3.二分查找的缺点
1)必须采用顺序存储结构。
2)必须按关键字大小有序排列。
说人话就是 数据得是数组,且从大到小 或者 从小到大 等进行排好序。
4.二分查找原理
针对已经排列好的数组,假如我判断6是否在这个数组内,如果是返回ture,否则返回false。
我们在数组的最左边定义一个left,在最右边定义为right,中间的mid则为(left+right)/2
我们用mid的值与6做对比,发现mid的值为5,6比5大,则mid左边的所有数据都抛弃掉,同时,我们把left的值设为mid+1,right保持不变
则left则到了6这个位置,则mid可以是7或者8这个位置,不影响操作。假设mid在的7位置
我们这时在比较6与mid的值比较,发现mid的值为7,6比7小,则mid右边的所有数据都抛弃掉,同时right变为mid-1
此时,我们的mid位置为(left+right)/2=6,mid的第6位置的值为6,是我们要查找的6,则 return true。
但是,假如我们查找的数不在这个数组里面呢?
首先,我们定义一串这样的数组a,要查找的数为60
定义a起始位置为left,末尾位置为right,则mid=(0+9)/2=4(4或者5都可以),a[mid]=a[4]=45
60比a[mid]=45大,所以我们可以舍弃mid左边所有的数据,同时,left=mid+1即left=5,right不变
此时mid=(left+right)/2=(5+9)/2=7,a[mid]=a[7]=74
同理,60小于74,则right=mid-1=6,left不变
此时只剩下两个值,mid=(5+6)/2=5或6,mid等于哪个都没问题,a[mid]=a[6]=67,我们要找的值是60,那我们继续分析的话,则right=mid-1,那left=mid=right,假如我们要找的数是67,我们就找到了,返回true,可惜我们现在找的是60,在走下去,依旧得不到结果,这样做就没有意义了,所以要使它有意义就必须满足left<=right,这便是我们进行二分查找的循环条件~~!
5.源代码实现
#include<stdbool.h> #include<stdio.h> bool halfsort(int need_num, int num[], int num_length); int main() { int a[] = { 11,18,22,34,45,53,67,74,89,99 }; int len = sizeof(a) / sizeof(a[0]); for (int i = 0; i < len; i++) { printf("正在检测[%d]:%d\n", a[i], halfsort(a[i], a, len)); } } bool halfsort(int need_num, int num[], int num_length) { bool ret = false; int left = 0; int right = num_length - 1;//计算出数组个数,数组中下标从0开始,需要-1 while (left <= right) { int mid = (left + right) / 2; if (num[mid] == need_num) { ret = true; break; } else if ( need_num < num[mid]) { right = mid - 1; } else { left = mid + 1; } } return ret; }
6.后话
分析原理的时候,可能说的有点乱,大概就是那样子,可以自己琢磨分析一下,enioy it~
这篇关于C语言程序设计:二分查找(折半查找)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-10-04el-table 开启定时器下,表格的选中状态会消失是什么原因-icode9专业技术文章分享
- 2024-10-03如何安装和初始化飞牛私有云 fnOS?-icode9专业技术文章分享
- 2024-10-03如何安装 App 并连接到飞牛 NAS?-icode9专业技术文章分享
- 2024-10-03如何安装飞牛 TV 并连接到影视服务器?-icode9专业技术文章分享
- 2024-10-03如何在PVE和ESXI上安装飞牛私有云 fnOS?-icode9专业技术文章分享
- 2024-10-03fnOS国产最强NAS安装系统异常情况处理-icode9专业技术文章分享
- 2024-10-03飞牛NAS如何创建存储空间?-icode9专业技术文章分享
- 2024-10-03fnOS国产最强NAS硬盘会自动休眠吗?-icode9专业技术文章分享
- 2024-10-03fnOS国产最强NAS如何安装飞牛影视和创建媒体库?-icode9专业技术文章分享
- 2024-10-03fnOS国产最强NAS如何为家人朋友开通影视账号?-icode9专业技术文章分享