给出折半查找的递归算法，并给出算法时间复杂度分析。

admin2019-08-15 41

问题给出折半查找的递归算法，并给出算法时间复杂度分析。

选项

答案 int BinSrch(rectype r[]，int k，low，high){ ／／在长为n的有序表中查找关键字k，若查找成功，返回k所在位置，查找失败返回O if(low＜=high){ ／／low和high分别是有序表的下界和上界 mid=(low+high)／2； if(r[mid]．key==k)return(mid)； else if(r[mid]．key＞k)retum(BinSrch(r，k，mid+l，high))； } else retum(BinSrch(r，k，low，mid一1))； } else retum 0：／／查找失败 } 算法时间复杂度为0(log₂n)。

解析

转载请注明原文地址:https://jikaoti.com/ti/XoGjFFFM

本试题收录于：计算机408题库学硕统考专业分类

计算机408

学硕统考专业

相关试题推荐

阅读下面史料，回答问题：材料一各缔约国主力舰替换总吨位按照标准排水量计算不得超过如下：合众国525000吨；英帝国525000吨；法国175000吨；意大利175000吨；日本315000吨。
某计算机有8个主设备需要竞争总线的使用权，其设备号为0～7。现欲设计其判优控制方法，试回答下述问题。(1)集中式总线判优控制与分布式总线判优控制的区别是什么?(2)若采用集中式判优控制，则在链式查询、计数器定时查询和独立请求三种方式下，
设计一个算法求图的中心点。设v是有向图G的一个顶点，把v的偏心度定义为：MAX{从w到v的最短距离｜w属于V(G))如果v是有向图G中具有的最小偏心度的顶点，则称顶点v是G的中心点。
一组记录的关键字为{25，50，15，35，80，85，20，40，36，70)，其中含有5个长度为2的有序表，用归并排序方法对该序列进行一趟归并后的结果是()。
设计一个算法，求无向图G(采用邻接表存储)的连通分量个数。
一棵：BS’r树共7个结点，值分别为1、2、3、4、5、6、7，形态为满二叉树，()不是插入序列。
设一段正文由字符集{A，B，C，D，E，F)中的字母组成，这6个字母在正文中出现的次数分别为{12，18，26，6，4，34)。(1)为这6个编码设计哈夫曼编码。(2)设每个字节由8位二进制位组成，试计算按哈夫曼编码压缩存储这段正文共需多少个字
给定序列{3，5，7，9，11，13，15，17)，(1)按表中元素的顺序依次插入一棵初始为空的二叉排序树，画出插入完成后的二叉排序树，并求在等概率情况下查找成功的平均查找长度。(2)按表中元素的顺序构造一棵平衡二叉树，并求其在等概率情
假设二叉树采用二叉链表存储结构存储，试设计一个算法，求出该二叉树中第一条最长的路径长度以及此路径上各结点的值。
下列叙述正确的个数是()。(1)m=2的平衡m路查找树是AVL树(2)m=3的平衡m路查找树是2—3树(3)m=2的平衡m路查找树的叶结点不一定在同一层(4)m阶B一树的叶结点必须在同一层(5)m阶B一树是平衡m路查找树(6)平衡m路查

随机试题

什么是不合格焊缝?对不合格焊缝的处理有哪些措施?
促销组合
工程选价控制的关键阶段是()。
就保险业而言，同一保险人不得同时兼营财产保险业务和人身保险业务。经营财产保险业务的保险公司可以依法经营的是(　　)。Ⅰ．短期健康保险业务Ⅱ．意外伤害保险业务Ⅲ．死亡保险Ⅳ．责任保险Ⅴ．财产保险业务
()是研究工作进行之初所做的书面规划，是如何进行研究的具体设想，是研究实施的蓝图。
最近，研究人员开发出一种新型锂电池，有望广泛用于笔记本电脑、手机等电子产品。传统的锂电池使用液态电解质，并用一层聚合物薄膜隔开正负极，而在这种新型锂电池中，电池的正负极被融合到一起，制作出一种类似果冻的胶状物。这种胶状物看起来是固态的，但其中70%的成分是
案例：甲因急用钱将乙委托其保管的一幅名画以自己的名义卖给丙，丙在支付对价的同时拿走了字画。一日乙在丙处见到自己的画欲拿回，遂与丙发生纠纷诉至法院。判决书：(注：法官拿到案件后，查遍当时所有法律，没有适用该案件的法条。于是甲、乙两法官分别写出自己的判决如下
设(1)用变限积分表示满足上述初值条件的特解y(x)；(2)讨论是否存在，若存在，给出条件，若不存在，说明理由．
若要用下面的程序片段使指针变量p指向一个存储整型变量的动态存储单元int*p；p=______malloc(sizeof(int));则应填入______。
It’sofficialthatmarriedpeoplearehealthier,oratleasttheythinktheyare.AnAmericansurveyof【C1】______100000people

最新回复(0)

给出折半查找的递归算法，并给出算法时间复杂度分析。

计算机408

学硕统考专业

阅读下面史料，回答问题：材料一各缔约国主力舰替换总吨位按照标准排水量计算不得超过如下：合众国525000吨；英帝国525000吨；法国175000吨；意大利175000吨；日本315000吨。

设计一个算法求图的中心点。设v是有向图G的一个顶点，把v的偏心度定义为：MAX{从w到v的最短距离｜w属于V(G))如果v是有向图G中具有的最小偏心度的顶点，则称顶点v是G的中心点。

一组记录的关键字为{25，50，15，35，80，85，20，40，36，70)，其中含有5个长度为2的有序表，用归并排序方法对该序列进行一趟归并后的结果是()。

设计一个算法，求无向图G(采用邻接表存储)的连通分量个数。

一棵：BS’r树共7个结点，值分别为1、2、3、4、5、6、7，形态为满二叉树，()不是插入序列。

假设二叉树采用二叉链表存储结构存储，试设计一个算法，求出该二叉树中第一条最长的路径长度以及此路径上各结点的值。

下列叙述正确的个数是()。(1)m=2的平衡m路查找树是AVL树(2)m=3的平衡m路查找树是2—3树(3)m=2的平衡m路查找树的叶结点不一定在同一层(4)m阶B一树的叶结点必须在同一层(5)m阶B一树是平衡m路查找树(6)平衡m路查

什么是不合格焊缝?对不合格焊缝的处理有哪些措施?

促销组合

工程选价控制的关键阶段是()。

就保险业而言，同一保险人不得同时兼营财产保险业务和人身保险业务。经营财产保险业务的保险公司可以依法经营的是( )。Ⅰ．短期健康保险业务Ⅱ．意外伤害保险业务Ⅲ．死亡保险Ⅳ．责任保险Ⅴ．财产保险业务

()是研究工作进行之初所做的书面规划，是如何进行研究的具体设想，是研究实施的蓝图。

设(1)用变限积分表示满足上述初值条件的特解y(x)；(2)讨论是否存在，若存在，给出条件，若不存在，说明理由．

若要用下面的程序片段使指针变量p指向一个存储整型变量的动态存储单元int*p；p=______malloc(sizeof(int));则应填入______。

It’sofficialthatmarriedpeoplearehealthier,oratleasttheythinktheyare.AnAmericansurveyof【C1】______100000people

就保险业而言，同一保险人不得同时兼营财产保险业务和人身保险业务。经营财产保险业务的保险公司可以依法经营的是(　　)。Ⅰ．短期健康保险业务Ⅱ．意外伤害保险业务Ⅲ．死亡保险Ⅳ．责任保险Ⅴ．财产保险业务

若要用下面的程序片段使指针变量p指向一个存储整型变量的动态存储单元int*p；p=malloc(sizeof(int));则应填入。