第4章执行搜索算法.ppt

第4章执行搜索算法
目标
在本章中,你将学习:
使用线性搜索技术搜索数据
使用二叉搜索技术搜索数据
使用散列法存储和搜索数据
线性搜索:
是最简单的搜索方法
也称作顺序搜索
用给定条目逐一与列表中的条目进行比较
执行线性搜索
线性搜索比较给定元素与列表中的第一个元素。
如果值不匹配:
则给定元素将与列表中的第二个元素作比较。
如果值还是不匹配:
则给定元素将与列表中的第三个元素作比较。
这个过程将一直持续下去,直到:
找到所需的元素或到达列表的未尾为止。
执行线性搜索
使用线性搜索算法编写一个算法以搜索员工记录列表中给定的员工的工号employee ID :
1. 读取要搜索的工号
2. 设置 i = 0
3. 重复步骤 4 直到 i > n 或 arr[i]==employee ID
4. i 值增加 1
5. 如果 i > n:
显示“未找到”
否则
显示“已找到”
执行线性搜索(续)
搜索算法的效率是由算法的运行时间决定的。
在最佳情况下:
元素位于列表的第一个位置。
比较次数为 1。
线性搜索的最佳的效率是O(1)。
在最差情况下:
元素位于列表中最后一个位置或者它根本不存在于该列表中。
比较次数为元素的数。
线性搜索最差的效率是O(n)。
确定线性搜索的效率
在平均情况下:
线性搜索的平均比较数由最佳和最差搜索中的平均比较数决定。
线性搜索的平均效率是(n + 1)/2。
确定线性搜索的效率(续)
您要在一个包含5000个元素的数组中应用线性搜索来搜索一个元素,如果在搜索的最后,您发现该元素不在该数组中,则为了在该给定的列表中搜索所需的元素您要进行多少次的比较?
课间思考
答案:
5,000
问题描述:
编写一个在含有最多20个数的数组中使用线性搜索算法搜索一个给定数的程序,如果要搜索的元素在列表中出现多次,则该程序应该显示第一次出现的位置,还应该显示所作的比较总数。
活动:执行线性搜索
二叉搜索算法:
用于搜索大列表
以十分少的比较来搜索数据
如果要搜索的列表已经排序,则可以使用二叉搜索算法
执行二叉搜索