VB大讲堂之对分查找(共14张PPT)

信息那些事儿 第七讲 那些查找 对分查找 查找 基本思想 一 猜数游戏 1. 对分查找有哪些要求？ 查找 基本思想 一 2. 对分查找的基本思想是什么？ 被查找数据必须是有序 首先将要查找的数据与待查找有序数组内处于中间位置的数据进行比较，如中间位置上的数与目标数据不同，根据有序性，就可确定应该继续在数组的前半部分还是后半部分查找。 在新确定的范围内，继续按上述方法进行查找，直到获得最终结果。 查找 基本思想 一 如何确定有序数组的“中间位置”？ 我们用i代表查找范围的头，j代表查找范围的尾， mid代表中间位置，如何用i和j表示mid？ mid=(i+j)/2 ? mid=(i+j)\2 mid=Fix((i+j)/2) mid=Int((i+j)/2) 查找 基本思想 一 请写出在数组a(1)-a(7)：1,22,33,44,55,66,77中查找目标key=55过程中i,j,mid,a(mid)的变化过程 i 1 j 7 mid 4 a(mid) 44 5 5 7 5 6 5 66 55(找到了) 查找 基本思想 一 请写出在数组a(1)-a(7)：1,22,33,44,55,66,77中查找目标key=11过程中i,j,mid,a(mid)的变化过程 i 1 j 7 mid 4 a(mid) 44 1 1 2 3 1 1 2 1 （头>尾？） 22 1 何时停下查找？ 查找 基本思想 一 Key与d(mid)的大小比较影响i,j的取值的规律： i的取值规律：if d(mid)<key then i=mid+1 j的取值规律：if d(mid)>key then j=mid-1 用分支结构实现。 继续进行重复查找的条件： i<=j，用循环结构实现。 当找到或者i>j是结束查找。 查找 流程图 二 Y Y N 开始 i1,j10 计算m