经验首页 前端设计 程序设计 Java相关 移动开发 数据库/运维 软件/图像 大数据/云计算 其他经验
当前位置:技术经验 » 程序设计 » C 语言 » 查看文章
用C语言实现二分查找算法
来源:jb51  时间:2022/1/17 16:40:52  对本文有异议

一.前言

假如今天我们需要在一个有序的数组中来寻找一个数的下标,就用"1,2,3,4,5,6,7,8,9"这九个数组成的数组来说,假如我们想寻找'2',那很简单我们只用从小到大开始寻找,寻找两次就完成了,但是我们想寻找'7',我们继续用从小到大挨个寻找,这就显得有点慢并且耗时长还没有效率,因此我们可以有一种全新的方法,二分查找法来解决这个问题。

二.二分查找法

1.什么是二分查找法

二分查找法,又叫做折半查找法,它是一种效率较高的查找方法。但是,折半查找要求线性表必须采用顺序存储结构,而且表中元素按关键字有序排列。就用刚刚的数组来说,我们想寻找'7',很简单我们先用7和数组中间的数来比较大小,很明显7大于,所以我们缩小范围,从中间的右边开始继续取中间值,继续寻找,直到找到位置,这样一看找的次数少了很多,而且速度也快了不少。

2.如何用c语言来实现二分查找法

咱们来分析一下刚刚我说的找数字7的过程,首先我们需要数组的中间的数也就是中间数的下标值,那我们就需要直到数组第一个元素和最后一个元素的下标值,数组第一个元素下标值很明显是0,我们把他定义成left;这个最后一个元素的下标值我们就需要利用sizeof来计算,我们把他定义成rigth。然后两个相加,算出最中间的下标,我们把他定义为mid,和要找的数进行比较,假如大于要找的数那就从mid+1和right之间来继续刚刚的循环,假如小于要找的数那我们就从left和mid-1之间寻找。就这样一直循环,直到找到目标数为止。

代码的实现如下

  1. void Findnum(int* arr, int key,int sz)//arr为目标数组,key为需要查找的数,sz为数组元素的大小
  2. {//二分查找
  3. int left = 0;//左边
  4. int right = sz-1;//右边
  5. while (left <= right)
  6. {
  7. int mid = (right + left) / 2;
  8. if (arr[mid] > key)
  9. {//说明key在arr[mid]和left之间
  10. right = mid - 1;
  11. }
  12. else if (arr[mid] < key)
  13. {
  14. left = mid + 1;
  15. }
  16. else
  17. {
  18. printf("找到了,对应的下标为:%d\n", mid);
  19. break;
  20. }
  21. }
  22. if (left > right)
  23. {
  24. printf("找不到\n");
  25. }
  26. }

最后运行

三.总结

关于上面的过程,我们不难发现二分查找法虽然很快,但是有两个很明显的缺点,一个是他实现的条件必须是一个有序的数列,另外一个是他只能一次性找一个数而不是多个,这就让他有了很多局限性。二分查找有个很重要的特点,就是不会查找数列的全部元素,而查找的数据量其实正好符合元素的对数,正常情况下每次查找的元素都在一半一半地减少。所以二分查找的时间复杂度为

log2o是毫无疑问的。

总结

到此这篇关于c语言实现二分查找法的文章就介绍到这了,更多相关c语言二分查找法内容请搜索w3xue以前的文章或继续浏览下面的相关文章希望大家以后多多支持w3xue!

 友情链接:直通硅谷  点职佳  北美留学生论坛

本站QQ群:前端 618073944 | Java 606181507 | Python 626812652 | C/C++ 612253063 | 微信 634508462 | 苹果 692586424 | C#/.net 182808419 | PHP 305140648 | 运维 608723728

W3xue 的所有内容仅供测试,对任何法律问题及风险不承担任何责任。通过使用本站内容随之而来的风险与本站无关。
关于我们  |  意见建议  |  捐助我们  |  报错有奖  |  广告合作、友情链接(目前9元/月)请联系QQ:27243702 沸活量
皖ICP备17017327号-2 皖公网安备34020702000426号