精华内容
下载资源
问答
  • 折半查找法

    2020-03-19 20:43:24
    文章目录折半查找法摘要概述引申解题步骤算法代码实现 折半查找法 摘要 折半查找法是效率较高的一种查找方法。假设有已经按照从小到大的顺序排列好的五个整数a0~a4,要查找的数是X,其基本思想是: 设查找数据的范围...

    折半查找法

    摘要

    折半查找法是效率较高的一种查找方法。假设有已经按照从小到大的顺序排列好的五个整数a0~a4,要查找的数是X,其基本思想是: 设查找数据的范围下限为l=1,上限为h=5,求中点m=(l+h)/2,用X与中点元素am比较,若X等于am,即找到,停止查找;否则,若X大于am,替换下限l=m+1,到下半段继续查找;若X小于am,换上限h=m-1,到上半段继续查找;如此重复前面的过程直到找到或者l>h为止。如果l>h,说明没有此数,打印找不到信息,程序结束。

    概述

    该方法是查找的范围不断缩小一半,所以查找效率较高。
    三角形加倍折半法 加倍折半法的关键是如何“加倍”、“折半”。那么“加倍”、“折半”的方法又是什么呢?传统的“加倍”的方法,是将线段延长一倍;传统的“折半”的方法,是取线段的中点。岂不知,“三角形中位线定理”、“直角三角形斜边上的中线等于斜边的一半”、“等腰三角形的三线合一性质”、“平行线等分线段定理”……均有“加倍、折半”的功用。也就是说“加倍”“折半”的方法是众多的、丰富的。而这些的方法基本上都是来自上述的一些重要的定理。
    例1 已知:△ABC中,AB=AC,延长AB到D,使DB=AB,E是AB的中点。求证:CD=2CE
    思路一:延长CE到F1,使EF1=CE,即用
    延长的方法将CE扩大一倍为CF1,证CF1=CD
    思路二:取CD的中点,即用“取中点”的方法将CD缩小一半为CF2,证CF2=CE。
    以上为“传统”的加倍折半法,引申后则有:
    思路三:抓住E为AB中点这一特点,作△ABF3,使CE为该三角形的中位线(过A作AF3∥CE,交BC的延长线于F3),即用三角形中位线定理将CE扩大一倍为AF3,证AF3=CD
    思路四:抓住B为AD中点这一特点,作△ADC以CD边为底边的中位线(过B作BF4∥CD,交AC于F4),即:用三角形中位线定理将CD缩小一半为BF4,证BF4=CE

    引申

    对三角形加倍折半法“用途”的引申
    传统的加倍折半法主要应用于线段(或角)倍半关系的证明。随着“方法”的引申,其功能也随之得到了增强。特别是完全领会了加倍折半法的基本思想后,许多疑难问题就会迎刃而解。它的用途远远超出了原先的范围,几乎适用于所有含“2”的类型题。下面,分“结论中含有2”和“题设中含有2”两中情况作简单的介绍。
    1、加倍折半法来解“结论中含有2”的类型题,实际上就是“分析法”的一种具体应用。“加倍折半法”在此起的作用,也可称之为“解题技巧”。例1属于该种类型的“传统”例题,下面举几个引申后的例子。
    例2 已知:△ABC中,D是BC上的中点,F是AD上的任意一点,延长CF交AB于E。求证:AF:DF=2AE:BE
    思路:本题的难点是如何除去比例式中的“2”
    方法一:将AE或DF“加倍”,由于D是BC的中点,
    过点B作BG∥DF,交CE的延长线于G,则用三角形中位线定理将DF“扩大一倍”为BG。这样,原题就有效的转化为证明AF:BG=AE:BE。
    方法二:是将AF或BE“折半”,由于D是BC的中点,过点D作DH∥AB,交CE于GH,则用三角形中位线的定理将BE“缩小一半”为DH。这样,原题就有效的转化为证明AF:DF=AE:DH。
    2、用加倍折半法来解“题设中含有2”的类型题,实际上就是“综合法”的一种具体的应用。“加倍折半法”在此起的作用,可称之为“解题经验”。
    例3 已知:△ABC中,AD是高线,∠ABC=2∠ACB。求证:CD=AB+BD
    思路:该题属于“截长补短法”的习题,
    折半查找法
    但由于已知条件中有角的倍半关系,因
    而用“加倍折半法”的思路也可以解决。
    思路一:延长DB到E1,使BE1=BA(造等腰三角形将∠ABC“折半“为E1),则∠E1=∠C,AE1=AC,CD=DE1,故CD=AB+BD
    思路二:作∠CAE2,使∠CAE2=∠C(造等腰三角形将∠C“加倍”为∠AE2B),则∠AE2B=∠ABC,AE2=E2C=AB,BD=DE2,故CD=AB+BD。

    在这里插入图片描述

    解题步骤

    1.定义3个用来记录索引值的变量,变量min记录当前范围最小索引值,初始值为0;变量max记录当前范围最大索引值,初始值为数组长度-1;变量mid记录当前当前范围最中间元素的索引值,初始值为(min+max) / 2
    2.使用循环,判断当前范围下,最中间元素值与指定查找的数值是否相等
    若相等,结束循环,返回当前范围最中间元素的索引值mid
    若不相等,根据比较结果,缩小查询范围为上一次查询范围的一般
    中间元素值 比 要查询的数值大,说明要查询的数值在当前范围的最小索引位置与中间索引位置之间,此时,更新查询范围为:
    范围最大索引值 = 上一次中间索引位置 -1;
    中间元素值 比 要查询的数值小,说明要查询的数值在当前范围的最大索引位置与中间索引位置之间,此时,更新查询范围为:
    范围最小索引值 = 上一次中间索引位置 +1;
    在新的查询范围中,更新中间元素值的位置,再次使用最中间元素值与指定查找的数值是否相等。
    中间索引值 = (范围最小索引值 +范围最大索引值) / 2;
    3.每次查询范围缩小一半后,使用if语句判断,查询范围是否小于0个元素,若小于0个元素,则说明指定数值没有查询到,返回索引值-1。

    算法代码实现

    
    int search(int* p, int number, int under, int top)
    {
        int mind = (under + top) / 2;  //二分法查找    
    
        if (mind < under || mind > top)
        {
            return 0;
        }
        else if (p[mind] < number)   
        {
            return search(p, number, mind + 1, top);
        }
        else if (p[mind] > number)
        {
            return search(p, number, under, mind - 1);
        }
        else return mind+1;
    }
    
    展开全文

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 2,093
精华内容 837
关键字:

折半查找法