从顺序查找到二分查找课件.ppt

1、从顺序查找到二分查找从顺序查找到二分查找查找查找n给定一个值Key，在含有n个元素的数组中找出等于给定值Key的元素。若找到，则查找成功，返回元素的信息或该元素在表中的位置；否则查找失败，返回相关的指示信息。顺序查找顺序查找n从数组的一端开始，顺序扫描数组，依次将扫描到的元素和给定值Key相比较。若当前扫描到的元素与Key相等，则查找成功；若扫描结束后，仍未找到元素等于Key的结点，则查找失败。开始输入待查找的值给变量keyi=1in？a(i)=key?Yi=i+1N输出“找不到”N输出“找到了”Y程序流程图程序流程图结束顺序查找的效率nn个元素的数组：n最快：1次n最慢：n次思考n如果数组是

2、有序的，有没有效率更高的算法？二分（对分）查找二分查找（在一个升序的数组里）二分查找（在一个升序的数组里）ni1:jn:key=120n确定查找的中点位置m=(i+j)2n将待找的Key与a(m)比较：若相等，则查找成功并返回此位置，查找结束。否则确定新的查找区间，继续二分查找：n若Keya(m)，则要找的Key可能在m的右子数组a(m.n)中，即新的查找区间是右子表a(m+1.n)。n2156789810110611012012513021567898101106110120125130Key=10621567898101106110120125130i=1j=10m=(i+j)2 =5i=

3、m16j=10m=8Keya(m)Keya(m)i=6j=m-1=7m=6Key=a(m)Key=6521567898101106110120125130i=1j=10m=5j=m-1=4mid=2Key a(m)m=3j=m-1=2i j还继续吗还继续吗?二分查找二分查找ni1，jnn确定查找的中点位置m=(i+j)2n将待找的Key与a(m)比较：若相等，则查找成功并返回此位置，查找结束。否则确定新的查找区间，继续二分查找：n若Keya(m)，则要找的Key可能在mid的右子数组a(m+1.n)中，即新的查找区间是右子表a(m+1.n)。nn找不到时结束的条件：i j开始输入待查找的值给变量keyi=1:j=nij？输出“找不到”N输出 mY程序流程图程序流程图结束keya(m)?NYj=m-1Ni=m+1Ym=(i+j)2a(m)=key?课堂实践课堂实践总结：顺序查找与二分查找总结：顺序查找与二分查找顺序查找二分查找对数组的要求无要求必须是有序的假设数组是有序的前提比较的次数=n=int(log2n)+1查找效率低高