顺序查找和对分查找.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,超过数组中元素个数,找不到 算法描述 取得要找的元素值key 从数组的第i个位置开始找(i开始等于1) 如果d(i)=key ,则输出i,并退出循环 否则i指向下一个位置,继续找 如果找到数组末尾还没找到,则输出找不到. 代码格式 k=0 for i=1 to n if a(i)=key then k=i next i if k 0 then print “查找成功”，“位置在第” k “个元素中” else print “查找不成功” end if For I=1 to n randomize d(i)=int(1000*rnd) Next i 怎样自动生成数据呢？ 利用随机函数rnd():产生[0,1)之间的随机数 顺序查找分析 若一个数组有n个元素 找到第1个元素,查找1次 找到第2个元素,查找2次 …… 找到第n个元素，查找n次 平均查找次数（1+2+……+n）/n （n+1）/2 例如： 对分查找的基本方法是 在查找范围(I,j)内，可以利用数据的有序性，而不必逐个地进行查找，计算查找范围的中点位置。把查找范围(I,j)的中点位置上的数据d(m)与查找键key进行比较，结果必然是如下三种情况之一： (1)keyd(m)，查找键小于中点d(m)处的数据。由数组d中数据的递增性可 以确定上：在(m,j)内不可能存在值为key的数据，必须在新的范围(I,m-1)中 继续查找。 (2)key=d(m)，找到了需要的数据。 (3)keyd(m)与(1)相同的理由，必须在新的范围(m+1,j)中继续查找。 这样除了出现情况(2)在通过一次比较后新的查找范围不超过上一次查找范围的一半。 对分查找分析 对分查找时每次都把查找范围缩小一半 因此平均的查找次数是log2n