查找算法课件.ppt

查找是一种查询数据的技术，其目标是能以比较少的步聚和较短的时间找到所需的对象。 顺序查找的基本思想 是从第一个数据开始，按数据的顺序逐个将数据与给定的值进行比较。若某个数据和给定的值相等，则查找成功，找到所查数据的位置；反之，查找不成功。 查找算法 27 36 32 18 d (1) d (2) d (3) d (4) 输入查找的元素值key=32 i=1 i=2 i=3 此时d(i)=key,数组中的第3个位置 如果输入查找的元素值key=22 i=1 i=2 i=3 i=4 i=5 27 36 32 18 d (1) d (2) d (3) d (4) 此时i等于5,超过数组中元素个数,找不到 从数组d的第1个元素d(1)开始，依次判断各元素的值是否与查找键key的值相等。 顺序查找的流程图 开始 i 1 d(i)=key? i=n? i　i+1 未找到，输出结果：0 找到，输出结果：i 结束 Y N Y N Private Sub Command6_Click() 顺序查找 Key = Val(Text2.Text) For i = 1 To num If d(i) = Key Then Label5.Caption = 在数组的 + Str(i) + 位置中 Exit For End If Next If i = num + 1 Then Label5.Caption = 在数组中没有找到 + Str(Key) End If End Sub 对分查找的基本思想 对分查找的前提是数据已经有序（以递增为例），然后把待查找的数据与数组中间位置的数比较，如果比中间位置的数大，在数组的后半部分继续查找，否则在数组的前半部分查找，继续对分查找，直到找到待查找的数在数组中的位置或数组已无法对分。 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 下标 元素 M=fix((i+j)/2) =8 I=1 J=16 第1次比较： Keyd(m) 查找范围应该 变成d(9)~d(16) Key=52 ①变量 I和J记录所要查找范围的起始和终止位置 过程： 10 15 17 18 22 27 35 45 48 52 65 67 72 85 97 98 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 下标 元素 10 15 17 18 22 27 35 45 48 52 65 67 72 85 97 98 J=16 M=fix((i+j)/2) =12 第2次比较： Keyd(m) 查找范围应该 变成d(9)~d(11) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 下标 元素 10 15 17 18 22 27 35 45 48 52 65 67 72 85 97 98 I=9 J=11 M=fix((i+j)/2) =10 第3次比较： Key=d(m) 找到了！ ②计算中间点M的位置：M=fix((i+j)/2) 或M= (i+j)\2 ③比较key和d(M)的值，根据结果重新确定查找的起始和终止位置或者直接告诉已经找到 J不变，I=M+1=9 I=9 I不变，J=M-1=11 顺序查找的流程图 开始 i 1 d(i)=key? i=n? i　i+1 未找到，输出结果：0 找到，输出结果：i 结束 Y N Y N Private Sub Command6_Click() 顺序查找 Key = Val(Text2.Text) For i = 1 To num If d(i) = Key Then Label5.Caption = 在数组的 + Str(i) + 位置中 Exit For End If Next If i = num + 1 Then Label5.Caption = 在数组中没有找到 + Str(Key) End If End Sub 在规模为n的数组变量d中进行对分查找的流程图 未找到，输出结果：0 开始 I←1 ，j←n i=j? 找到，输出结果：m 结束 N Y 计算中点m← (i+j)\2 d(m)=key? D(m)key? i←m+1 j←m-1 Y Y N N 自然语言描述对分查找： 1、（确定初始查找范围）i?1,j?n 2、（是否继续查找？）如果i=j,那么转到4 3、（找不到）输出结果，算法结束 4、（计算中点位置）m?(i+j\2) 5、（相等？）d(m)=key,那么转到7 6、（修改查找范围）如果keyd(m)那么j?m-1,