C语言——折半查找法

这篇具有很好参考价值的文章主要介绍了C语言——折半查找法。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

一、使用场景

假如现在有一组数据,你想要查询这个具体某一个数据在这一堆数据中的所在位置,这个时候就需要程序在这一组数据中,找到与想要查找的目标数据相匹配的那个数据,然后返回相对应的位置。如果将问题再细化简化一点,假如现在有一组有顺序的数字,需要你编写程序找到其中一个数字所在的位置。了解需求之后,我们脑海中一般首先浮现的思路便是,编写一个数组,然后将数字一个个进行匹配,最后找到这个数字的位置,返回该位置,问题解决。

现在我们就将此思路实践一下看看是否能够找到该数字。给出一个包含十个元素的数组,里面包含了1,2,3,4,5,6,7,8,9,10,然后尝试在其中找到数字7对应的位置,代码如下所示:

折半查找法,C语言语法基础,c语言,算法

折半查找法,C语言语法基础,c语言,算法

上面的代码使用了flag作为一个标志数,因为成功找到后break跳出循环继续执行,但是如果查找的是一个不存在该数组中的数字时,对上面数据全部进行查找之后也会结束循环执行,此时如果没有标志数,程序就无法判断是因为哪种原因跳出了循环结构。所以定义一个变量flag进行判断:如果成功找到,flag的值为1,否则为0,程序就能通过if语句进行判断是哪种情况,判断是否输出找不到情况下的语句。

我们发现最后是可以实现这个目标的,成功找到了数字7在这个数字中对应的位置:7.(这个位置是指在数字的位置而不是数组中的下标)。

但是这样一个个数字进行匹配,虽然能找到对应位置,但是假如现在有100或者1000甚至10000个数字,然后想要找到比较靠后的一个数字对应的位置时,这种方法就显得有些许“笨拙”了,不够灵活和简便,要将所有数字从头到尾一个个进行匹配,直至找到为止。此时就需要使用一个更加简便更加快速的方法——折半查找法,或者叫做二分查找法。

二、如何实现折半查找法

假如一天你的同学买了一双球鞋,只告诉你这双鞋在一千以内,然后让你猜这双鞋价格是多少,你会怎么做?可能有少部分人会上来就给这位朋友一拳,然后一顿输出“你买鞋又不是买给我,还**让我猜价钱,凡尔赛你**,我******”,但是大多数人还是会选择正确的做法:从中间数500开始猜,而不是像上面的做法一样,真的就傻傻的从1,2,3开始猜到1000。所以折半查找法的思想也是如此。

我们从这一组有序数字中,取其中位数与我们查找的目标数进行匹配,如果正好一发入魂,那就直接找到了该数,但是即使大概率不正确,我们也可以直接干掉一半的数据。举个例子:假如现在有个数组是1-1000,目标数是777,那么我中位数是500,进行比较之后是比目标数更小,那就说明目标数的位置只可能在中位数往上,而不能在500之下,那么500以下的数字就全部被干倒了,这一次查找就可以消灭掉一半数据,而上面的做法一次只能消灭一个数字,效率相比之下就产生了很明显的差距了。然后第一次查找后再进行第二次折半,取750进行比较,这次还是比目标数小,但是仍然干掉了一半数据,依次进行下去,只需使用少数次数查找便可以从大量数据中找到。

现在还是使用上面的例子,示例以下折半查找法:

折半查找法,C语言语法基础,c语言,算法

 上面代码中先定义了一个左下标和右下标,从而定义出中位数的下标。每次查找之后,如果目标数 > 中位数,那么目标数只会出现在中位数往上的位置,那么此时右下标不需变动,左下标应该是中位数的下标 +1,再次对左右下标相加除以2,取得剩下数据的中位数作为新的中位数进行下一次查找。如果目标数 < 中位数,那么目标数只会出现在中位数之下的位置,那么此时左下标不需变动,右下标应该是中位数的下标 -1,然后再次取新的中位数,以此类推进行查找,所以使用while循环。

第一次查找的图示如下,第一次查找之后可知 k > 中位数,所以 k 的位置只可能出现在中位数的右边,此时我们的第二次查找想要从中位数的右边第一个数开始找起,所以此时左下标应该是 mid + 1。

折半查找法,C语言语法基础,c语言,算法

 所以第二次查找如下,可知现在 k < 中位数,所以只可能出现在中位数的左边,此时我们希望下次查找从中位数的左边第一个数开始,所以此时右下标为 mid - 1。

折半查找法,C语言语法基础,c语言,算法

 然后后续查找都如上图所示,直至左右下标交错(left > right)或者相等(left = right),便是循环结束的标志。

折半查找法,C语言语法基础,c语言,算法

 折半查找法,C语言语法基础,c语言,算法

 三、总结

折半查找法每一次查找都可以判断一半数量的数据是否匹配,效率比第一种方法高效很多。k = 7 这种情况是查找次数最多的情况,都只需要四次查找即可完成,但是第一种方法查找需要七次,相比之下,足以见得折半查找法的高效性。

但是折半查找法也是需要前提条件才可以使用的,就是要求查找的这组数据必须是有序的,倒序和顺序都可以。面对无序的数据,折半查找法就失效,这也是相较于第一种方法的不足之处,两种方法各有所长,须根据不同情况进行使用。文章来源地址https://www.toymoban.com/news/detail-788758.html

到了这里,关于C语言——折半查找法的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 折半查找算法(BinarySearch)

            查找算法是一种在数字列表中确定目标元素所在位置的算法。假设给定一个目标元素 11 和一个包含元素 11 的数字列表(例如 10, 11, 12,13,14, 15, 16, 17, 18, 19, 20),然后在该数字列表中找到目标元素的位置。         折半查找算法也叫做对分查找和二分查找。折半

    2024年02月03日
    浏览(40)
  • 用Java(C语言也可以看)实现冒泡排序和折半查找(详细过程图)+逆序数组

      目录 一、冒泡排序 1.冒泡排序介绍 2.排序的思路 3.完整代码 二、折半查找 1.折半查找介绍 2.查找的思路 3.完整代码 三、逆序数组 1.逆序思路 2..完整代码 冒泡排序是众多排序的一种,无论在C语言或者Java中都很常见,后续在数据结构中也会用到 1.冒泡排序介绍 (1)冒泡排

    2024年02月05日
    浏览(43)
  • 折半插入排序算法详解之C语言版

    折半插入排序是插入排序方法中一种,相比较与直接插入排序算法,减少了排序过程中比较次数,也是一种常用的排序算法。 折半插入排序算法基本原理是将折半查找方法与直接插入排序方法相结合,也就是在每一次插入新元素时,利用折半查找方法找到其待插入的位置。

    2024年02月12日
    浏览(36)
  • 折半查找、

    描述 给定一个已按从大到小排序好的数组和一个数,使用折半查找算法,输出该数在数组中的位置。如果该数不在数组中,则输出“无此数”。 输入 输入为两行,第一行包含多个整数,用空格分隔,表示已排序好的数组;第二行为需要查找的数。 输出 输出一个整数,表示

    2024年02月14日
    浏览(72)
  • 折半查找的判定树

    二叉判定树是用于描述解决问题的思路,比如可以使用判定树描述N个数的比较过程,是一种对过程的描述。 它也可以用于描述二分查找(即折半查找,以下都作二分查找)的过程。 描述二分查找的二叉判定树,我们也可以叫折半查找判定树, 从这样的判定树,我们可以分析

    2024年02月08日
    浏览(31)
  • 折半查找实验 (数据结构)

    一、实验目的 掌握折半查找算法的基本思想 掌握折半查找算法的实现方法 掌握折半查找的时间性能 掌握折半查找类的定义和使用 二、实验要求 熟悉C++语言编程 了解折半查找的原理 了解折半查找类的定义、应用 三、实验内容 1、问题描述 在一个有序序列中,折半查找一个

    2024年02月08日
    浏览(84)
  • 折半查找(二分查找)的两种方法及实现 Python

    概念: 在计算机科学中,折半查找,也称二分查找,是一种在有序数组中查找某一特定元素的搜索算法。 搜索过程从数组的中间元素开始,如果中间元素正好是要查找的元素,则搜索过程结束;如果某一特定元素大于或者小于中间元素,则在数组大于或小于中间元素的那一

    2024年02月09日
    浏览(39)
  • 17-数据结构-查找-(顺序、折半、分块)

            简介:查找,顾名思义,是我们处理数据时常用的操作之一。大概就是我们从表格中去搜索我们想要的东西,这个表格,就是所谓的查找表(存储数据的表)。而我们怎么设计查找,才可以让计算机更快的去找到筛选我们所需要的信息呢,因此,关于怎么设计查找

    2024年02月09日
    浏览(55)
  • C++数据结构之查找——静态查找表(顺序查找、折半查找、分块查找 带有gif以及图示)

    目录 一、查找的相关概念介绍 1.查找表(Search Table) 概念 对查找表的操作 查找表的分类 2.(Key) 概念 3.查找(Searching) 概念 4.衡量查找算法的标准 1.时间复杂度 2.空间复杂度 3.平均查找长度(ASL) 二、静态查找表 1.顺序查找 算法思路 算法举例 算法性能分析 不等概率

    2024年02月03日
    浏览(44)
  • 二分(折半查找)详细解答(边界条件终止条件等等详细解释)

    刷 Leetcode 总能遇到关于二分的题目,但是之前也只是草草地了解一下,每次在使用的时候都需要找模板,要不然就需要对于边界条件进行调试,着实是很麻烦!!! 首先来简单介绍一下二分:二分查找也称折半查找(Binary Search),它是一种效率较高的查找方法。但是,折半

    2024年02月05日
    浏览(51)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包