文章详情

短信预约-IT技能 免费直播动态提醒

请输入下面的图形验证码

提交验证

短信预约提醒成功

一篇文章带你了解C语言二分查找的简单应用

2024-04-02 19:55

关注

前言

在有序数组中查找具体的某个数字n,可能有同学会说一个一个找,但是这样的效率实在太低,特别是对于有序的数组,效率太低。我们一般从中间元素开始找,查一次去掉一半数字,这种方法我们给它取名为折半查找即为二分查找,效率大大提高!怎么理解呢?如果有2的32次方个数字,我们最多只需查找32次,而一个一个数运气不好却是2的32次方次。

实战演练

这里我们先给出所写代码以及运行结果 

 

在这里,给大家分析一下,首先,我们先创建一个有序数组arr[],然后我们把要查找的7用int k表示,我们要确定这组数组的左下标0,右下标为sz-1,sz为数组的元素个数,即int left = 0,int right = sz-1;我们还要计算一下数组的元素总个数int sz =sizeof(arr)/sizeof(arr[0]);然后我们还需找出平均值int mid,如果arr[mid] < k,此时左下标left = mid+1,当arr[mid] > k,右下标right = mid-1,最后只剩一种情况直接打印break;出我们要求的mid,但是这只是一次查找,但是真正的二分查找需要好多次,那我们就需要让它循环while起来,需要一个条件left<=right,这说明中间还有元素,直到我们找到,但是当left>right时,此时我们可以大胆说明找不到,具体的代码如上图所示,这便是整个过程。小伙伴们赶紧int main(),return 0;敲起来试一试吧。

在这里,我在介绍另一种方法,通过函数的调用实现我们的二分查法。

 这里的思路主要跟上一种方法的思路差不多,在这里说明一下不能用0 == ret,虽然说0为假,非0为真,但是在这组数组中1的下标就是为0,在这里提醒一下各位,另外,千万不能不传sz,即不能把int sz放在函数那一块区域里求,这种写法是有问题的,什么问题呢?这里简单说明一下,问题在于此时求的sz不是10,而是1,为什么?数组arr传参,实际传递的不是数组的本身,仅仅传过去了数组首元素的地址,即为a的指针,实际上int a[]只是挂羊皮卖狗肉,本质上是指针,所以在函数不能在函数内部求,根本求不出元素个数,另外,在int a []不需要写数字大小,没有意义,希望大家能够理解,int a []并不会真正创建一个数组,大家一定要注意,未来如果我们遇到函数内部需要参数部分传过来元素个数,一定是在外部求好元素个数的,大家一定要多加注意,即在函数内部求元素个数是做不到的。

思路分析

最后,在这里总结一下思路,进行思路分析,二分查找是要求所查找数组的顺序必须是有序的,我们定义left为最左端的元素,right为最右端的元素,mid=(left+right)/2为数组的中间位置,然后用所查找的值的位置与mid所处的位置进行比较,如果比mid小,只需在数组的前半部分查找,如果比mid大,在数组的后半部分查找,以此类推,直到查到到所寻找的值不在该数组为止,这便是整体的思路。

总结

本片文章就到这里了,希望能够给你带来帮助,也希望您能够多多关注编程网的更多内容!

阅读原文内容投诉

免责声明:

① 本站未注明“稿件来源”的信息均来自网络整理。其文字、图片和音视频稿件的所属权归原作者所有。本站收集整理出于非商业性的教育和科研之目的,并不意味着本站赞同其观点或证实其内容的真实性。仅作为临时的测试数据,供内部测试之用。本站并未授权任何人以任何方式主动获取本站任何信息。

② 本站未注明“稿件来源”的临时测试数据将在测试完成后最终做删除处理。有问题或投稿请发送至: 邮箱/279061341@qq.com QQ/279061341

软考中级精品资料免费领

  • 历年真题答案解析
  • 备考技巧名师总结
  • 高频考点精准押题
  • 2024年上半年信息系统项目管理师第二批次真题及答案解析(完整版)

    难度     813人已做
    查看
  • 【考后总结】2024年5月26日信息系统项目管理师第2批次考情分析

    难度     354人已做
    查看
  • 【考后总结】2024年5月25日信息系统项目管理师第1批次考情分析

    难度     318人已做
    查看
  • 2024年上半年软考高项第一、二批次真题考点汇总(完整版)

    难度     435人已做
    查看
  • 2024年上半年系统架构设计师考试综合知识真题

    难度     224人已做
    查看

相关文章

发现更多好内容

猜你喜欢

AI推送时光机
位置:首页-资讯-后端开发
咦!没有更多了?去看看其它编程学习网 内容吧
首页课程
资料下载
问答资讯