顺序查找与二分查找复习
查找 给定一个值Key，在含有n个元素的数组中找出等于给定值Key的元素。若找到，则查找成功，返回元素的信息或该元素在表中的位置；否则查找失败，返回相关的指示信息。
顺序查找 从数组的一端开始，顺序扫描数组，依次将扫描到的元素和给定值Key相比较。若当前扫描到的元素与Key相等，则查找成功；若扫描结束后，仍未找到元素等于Key的结点，则查找失败。
程序流程图 N 开始 输入待查找的值给变量key i=1 i<＝n ？ Y Y 输出“找不到” a(i)=key ? N 输出“找到了” Y 结束
课堂任务 请写出顺序查找的程序。
二分（对分）查找
二分查找（在一个升序的数组里） i＝1 : j＝n : key=120 确定查找的中点位置m=(i+j)\2 将待找的Key与a(m)比较：若相等，则查找成功并返回此位置，查找结束。否则确定新的查找区间，继续二分查找： 若Key<a(m) ，则要找的Key可能在m左边的子数组a(1..m-1)中，故新的查找区间是左子数组a(1..m-1)中。 若Key>a(m) ，则要找的Key可能在m的右子数组a(m..n)中，即新的查找区间是右子表a(m+1..n) 。 ……
Key=106 21 56 78 98 101 106 110 120 125 130 21 56 78 98 101 106 110 120 125 130 21 56 78 98 101 106 110 120 125 130 i=1 m=(i+j)\2 =5 i=6 i=m＋1 ＝6 m=6 Key>a(m) Key=a(m) j=m-1 =7 m=8 Key<a(m) j=10 j=10
Key=65 21 56 78 98 101 106 110 120 125 130 21 56 78 98 101 106 110 120 125 130 i=1 21 56 78 98 101 106 110 120 125 130 i=1 mid=2 i=3 Key > a(m) m=3 j=m-1 =4 j=4 m=5 j= m-1=2 i > j 还继续吗?? Key < a(m) j=10
二分查找 i＝1，j＝n 确定查找的中点位置m=(i+j)\2 将待找的Key与a(m)比较：若相等，则查找成功并返回此位置，查找结束。否则确定新的查找区间，继续二分查找： 若Key<a(m) ，则要找的Key可能在m左边的子数组a(1..m-1)中，故新的查找区间是左子数组a(1..m-1)中。 若Key>a(m) ，则要找的Key可能在mid的右子数组a(m+1..n)中，即新的查找区间是右子表a(m+1..n) 。 …… 找不到时结束的条件： i > j
程序流程图 N N N Y i=m+1 开始 输入待查找的值给变量key i=1 : j = n i<＝j ？ Y m=(i+j)\2 输出“找不到” N Y m=(i+j)\2 a(m)=key ? 结束 输出 m Y key<a(m)? N N i=m+1 Y j=m-1
课堂实践
顺序查找与二分查找 顺序查找 二分查找 对数组的要求 无要求 必须是有序的 假设数组是有序的前提 比较的次数 <=n <=int(log2n)+1 查找效率 低 高