第18课 数据查找1——查找算法基础-【精彩三年】2024-2025学年高中信息技术选择性必修1课程探究与巩固Word教参(浙教版2019)

| 26页
| 82人阅读
| 2人下载
教辅
浙江良品图书有限公司
进店逛逛

新版页眉

学科网 zxxk.com学科网 zxxk.com

第18课 数据查找1——查找算法基础(见学生用书P114)

 

——5.4 数据查找,教材P147~158

1.理解查找的概念和基本方法。 2.理解顺序查找的思想,能利用顺序查找算法设计程序解决实际问题。 3.理解二分查找的思想,能利用二分查找算法设计程序解决实际问题 。

查找(Search)又称检索,计算机根据所给条件查找出满足条件的对象,即在存储的一批数据内寻找出一个特定的数据,或者确定在该批数据内是否存在这样的数据。若没有找到满足条件的对象,则返回特定值,表明查找失败;若查找到满足条件的对象,则表明查找成功,一般要求返回该对象的存储位置或对象值本身。

1.顺序查找

(1)顺序查找(Sequential Search)又称线性查找,从顺序表的 一端 开始, 依次 将每个元素的关键字与给定值key(查找键)进行比较。若某个元素的关键字等于key,则表明查找 成功 ;若所有元素都比较完毕仍找不到,则表明查找 失败 。

               顺序查找过程实例

(2)顺序查找的特点

①顺序查找将待查找的数值与序列中的数逐个进行比较,直到找出与给定数值相同的数为止,其算法简单,时间复杂度为 O(n) 。page number 0

独家授权

学科网 zxxk.com学科网 zxxk.com学科网(北京)股份有限公司


新版页眉

学科网 zxxk.com学科网 zxxk.com

②对存放数据的表结构无任何要求,不管数据 是否有序 ,均可适用。

③顺序查找算法的平均比较次数为:(n+1)/2。

(3)顺序查找算法实现

①在规模为n的数组d 中进行顺序查找的流程图如下所示:

             顺序查找算法流程图

②程序代码:

 

程序代码1

程序代码2

d=[25,22,13,18,14,11,17,19]

key=int(input(”输入需要查找的数: ”))

flag=False

n=len(d)

for i in range(n):

if d[i]==key:

flag=True

break

if flag==True:

def seq_search(s,a):

n=len(s)

flag=False

n=len(d)

for i in range(n):

if d[i]==key:

flag=True

break

if flag==True:

page number 1

独家授权

学科网 zxxk.com学科网 zxxk.com学科网(北京)股份有限公司


新版页眉

学科网 zxxk.com学科网 zxxk.com

print(”查找成功! ”)

else:

print(”未找到! ”)

return ”查找成功! ”

else:

return ”未找到! ”

d=[25,22,13,18,14,11,17,19]

key=int(input(”输入需要查找的数: ”))

result=seq_search(d,key)

print(result)

③运行结果:

输入需要查找的数: 18

查找成功!

输入需要查找的数: 20

未找到!

2.二分查找

(1)二分查找(Binary Search)又称折半查找、对分查找。它是一种效率很高的查找方法,但被查找的数据序列必须是有序的。

(2)二分查找首先将查找键与有序数组内处于中间位置的元素进行比较,如果中间位置上的元素的数值与查找键不同,根据数组元素的有序性,就可确定在数组的前半部分还是后半部分继续查找;在新确定的范围内,继续按上述方法进行查找,直到获得最终结果。

二分查找的算法时间复杂度为O(log2n)。二分查找的前提是数据有序,对n个数据查找,最多查找次数为int(log2n)+1。

(3)查找过程

若key为查找关键字,数组d存放n个已按升序排序的数据。使用二分查找时,把查找page number 2

独家授权

学科网 zxxk.com学科网 zxxk.com学科网(北京)股份有限公司


由于学科网是一个信息分享及获取的平台,不确保部分用户上传资料的 来源及知识产权归属。如您发现相关资料侵犯您的合法权益,请联系学科网,我们核实后将及时进行处理。