查找

(共10张PPT)
基本算法：查找
查找
定义：给定一个值K，在含有n个结点的表中
找出关键字等于给定值K的结点。若找到，
则查找成功，返回该结点的信息或该结点在
表中的位置；否则查找失败，返回相关的提
示信息。
分为：顺序查找、二分查找
顺序查找
是一种最简单的查找方法
基本思想：
从表的一端开始，顺序扫描线性表，依次将
扫描到的结点关键字和给定值K相比较，若
相等则查找成功；若扫描结束后，仍未找到
则查找失败。
顺序查找
顺序查找的算法：
VAR K:ktype; R:array [1..n] of ktype;
t = false;
for i:=1 to n do
if R[i]=k then begin t:=true; break; end;
if t then writeln( i ) else writeln(‘No answer!’);
顺序查找
算法分析：
平均查找长度ASL
ASL = (n+…+2+1)/n = (n+1)/2 成功
ASL = n 不成功
优点：适合线性表、链式表
缺点：效率低，当n较大时，不宜采用顺序查找
二分查找（折半查找）
是一种效率较高的查找方法
要求：线性表是有序表
基本思想：（设R[low..high]当前查找区间）
确定中间位置mid=[(low+high)/2]
将R[mid]与给定值K比较，若相等，则查找成功返回此位置；否则须确定新的查找区间，继续用二分查找。
若R[mid]>K，则新的查找区间是左子表R[1..mid-1]
若R[mid]二分查找算法：
Procedure binsearch ( VAR R:array[1..n] of ktype; K:ktype );
VAR low,high,mid :integer;
BEGIN
low:=1; high:=n;
while low<=high do
begin
mid:=(low+high) div 2;
if R[mid]=K then begin writeln(mid); exit; end;
if R[mid]>K then high:=mid-1 else low:=mid+1;
end;
writeln(‘No answer!’);
END;
二分查找
算法分析
优点：效率高
缺点：
只适合线性表，链表上无法实现二分查找
有序表
练习
1、对18个元素的有序表作二分查找，则查找A[3]的比较序列的下标为（ ）
A、1-2-3 B、9-5-2-3
C、9-5-3 D、9-4-2-3
2、在顺序表（2，5，7，10，14，15，18，23，35，41，52）中，用二分查找12，所需的关键字比较的次数为（ ）
A、2 B、3 C、4 D、5
D
C
练习
3、利用逐点插入法建立序列{50，72，43，85，75，20，35，45，65，30}对应的二叉排序数以后，查找元素35要进行（ ）元素间的比较。
A、4次 B、5次
C、7次 D、10次
A