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

《从顺序查找到二分查找课件.ppt》由会员分享，可在线阅读，更多相关《从顺序查找到二分查找课件.ppt（14页珍藏版）》请在三一办公上搜索。

1、从顺序查找到二分查找,查找,给定一个值Key，在含有n个元素的数组中找出等于给定值Key的元素。若找到，则查找成功，返回元素的信息或该元素在表中的位置；否则查找失败，返回相关的指示信息。,顺序查找,从数组的一端开始，顺序扫描数组，依次将扫描到的元素和给定值Key相比较。若当前扫描到的元素与Key相等，则查找成功；若扫描结束后，仍未找到元素等于Key的结点，则查找失败。,开始,程序流程图,顺序查找的效率,n个元素的数组：最快：1次最慢：n次,思考,如果数组是有序的，有没有效率更高的算法？,二分（对分）查找,二分查找（在一个升序的数组里）,i1:jn:key=120确定查找的中点位置m=(i+j)

2、2将待找的Key与a(m)比较：若相等，则查找成功并返回此位置，查找结束。否则确定新的查找区间，继续二分查找：若Keya(m)，则要找的Key可能在m的右子数组a(m.n)中，即新的查找区间是右子表a(m+1.n)。,Key=106,Keya(m),Keya(m),Key=a(m),Key=65,Key a(m),Key a(m),二分查找,i1，jn确定查找的中点位置m=(i+j)2将待找的Key与a(m)比较：若相等，则查找成功并返回此位置，查找结束。否则确定新的查找区间，继续二分查找：若Keya(m)，则要找的Key可能在mid的右子数组a(m+1.n)中，即新的查找区间是右子表a(m+1.n)。找不到时结束的条件：i j,开始,程序流程图,课堂实践,总结：顺序查找与二分查找,