Problem 2305 --习题6-9 折半查找

2305: 习题6-9 折半查找

上一题 正确率: $56.09\%$ 下一题
"
Time Limit $1$ 秒/Second(s) Memory Limit $512$ 兆字节/Megabyte(s)
提交总数 $731$ 正确数量 $410$
裁判形式 标准裁判/Standard Judge 我的状态 尚未尝试
难度 分类标签 二分

Description

有10个整数已按从小到大的顺序排好序，存储在一个数组中，再输入一个数，要求用折半查找法找出该数是数组中的第几个元素（输出该元素的下标即可）。如果该数不在数组中，则输出"Not exist!"

Input

输入数据共2行

第一行10个整数，按从小到大的顺序输入，中间以空格分隔。

第二行1个整数

Output

折半查找所得该数所在数组中的元素下标，单独占一行。

若该数不存在，则输出一行信息 "Not exist!"

Sample Input复制

1 2 3 4 5 6 7 8 9 10
3

Sample Output复制

2

提示

折半查找法也称为二分查找法，它充分利用了元素间的次序关系，采用分治策略，可在最坏的情况下用O(log n)完成搜索任务。它的基本思想是，将n个元素分成个数大致相同的两半，取a[n/2]与欲查找的x作比较，如果x=a[n/2]则找到x，算法终止。如 果x<a[n/2]，则我们只要在数组a的左半部继续搜索x（这里假设数组元素呈升序排列）。如果x>a[n/2]，则我们只要在数组a的右半部继续搜索x。

推荐代码 查看2305 所有题解 上传题解视频得图灵币

本题记录 用 户（点击查看用户） 运行号（点击购买题解） 时 间
算法最快[$0 $ms] 我要打十个 895948 2022-07-22 09:56:52
内存最少[$0 $KB] 千年孤独 574730 2020-03-26 21:09:01
第一AC 范晋豪@信息与计算科学142 153233 2017-11-16 15:12:39
第一挑战 范晋豪@信息与计算科学142 153233 2017-11-16 15:12:39

赛题来源/所属竞赛 C语言第四版教学实验-第六章 数组 C程序设计(第四版)

竞赛编号 竞赛名称 竞赛时间 访问比赛
1632 2021《图灵信息学算法》中级班第6单元-查找+二分法 2021-04-17 16:00:00 请登录
1551 2020-2021-1学期《Python程序设计》循环和列表【20数据科学12班】 2020-10-22 10:00:00 请登录
1486 2019-2020-1学期《C语言程序设计技能实训》第二场：数组【19计算机12班】 2019-11-30 19:00:00 请登录
1422 2019《图灵信息学算法》中级班第6单元:查找和二分算法 2019-11-03 15:40:00 请登录
1415 2019-2020-1学期《Python程序设计》循环和列表【19数据科学123班】 2019-10-22 10:00:00 请登录