1、信息那些事儿信息那些事儿第七讲第七讲 那些查找那些查找对分查找对分查找查找基本思想一一猜数游戏猜数游戏1.对分查找有哪些要求？对分查找有哪些要求？查找基本思想一一2.对分查找的基本思想是什么？对分查找的基本思想是什么？被查找数据必须是被查找数据必须是有序有序 首先将要查找的数据与待查找有序数组内处于中间位置的数据首先将要查找的数据与待查找有序数组内处于中间位置的数据进行比较，如中间位置上的数与目标数据不同，根据有序性，进行比较，如中间位置上的数与目标数据不同，根据有序性，就可确定应该继续在数组的前半部分还是后半部分查找。就可确定应该继续在数组的前半部分还是后半部分查找。在新确定的范围内，继续按
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(mi
3、d)的变化过程的变化过程i 1 j 7mid 4a(mid)445 57 56 566 55(找到了找到了)查找基本思想一一请写出在数组请写出在数组a(1)-a(7)：1,22,33,44,55,66,77中查找目标中查找目标key=11过程中过程中i,j,mid,a(mid)的变化过程的变化过程i 1 j 7mid 4a(mid)441 1 23 1 12 1 （头（头尾？）尾？）22 1何时停下查找？何时停下查找？查找基本思想一一 Key与与d(mid)的大小比较影响的大小比较影响i,j的取值的规律：的取值的规律：i的取值规律：的取值规律：if d(mid)key then j=mid-1
4、 用分支结构实现。用分支结构实现。继续进行重复查找的条件：继续进行重复查找的条件：ij是结束查找。是结束查找。查找流程图二二YYN开始开始i1,j10计算计算midd(mid)=key?Nimid+1jmid-1N继续查找？继续查找？输出输出“未找到未找到”Y输出找到的信息输出找到的信息结束结束d(mid)key?Do while i=jmid=(i+j)2程序实现三三年年请结合流程图写出对分查找核心伪代码？请结合流程图写出对分查找核心伪代码？已知：被查找数据已经存储在数组已知：被查找数据已经存储在数组d中并是有序的中并是有序的程序实现三三年年Do While i=j mid=(i+j)2 I
5、f d(mid)=key Then Text2.Text=找到了，是第找到了，是第&mid&个个 Exit Do Else If d(mid)key Then i=mid+1 Else j=mid-1 End If Loop 对分查找的对分查找的“中间位置中间位置”是如何确定？有哪些表示方式？是如何确定？有哪些表示方式？查找对分查找的一些变形四四mid=Int(i+j)/2+0.5)mid=(i+j+1)2 mid=Fix(i+j+1)/2)mid=Int(i+j+1)/2)mid=(i+j)2 mid=Fix(i+j)/2)mid=Int(i+j)/2)对分查找的一些变形四四Do While
6、 i=j And f=false s=s+1 mid=(i+j)2 If d(mid)=key Then Text2.Text=找到了，是第找到了，是第&mid&个个 f=True Else If d(mid)key Then i=mid+1 Else j=mid-1 End If Loop对分查找的一些变形四四Do While i=j And f=false s=s+1 mid=(i+j)2 If d(mid)=key Then Text2.Text=找到了，是第找到了，是第&mid&个个 f=True End If If d(mid)key Then i=mid+1 Else j=mid-1 End If LoopThanks信息那些事儿信息那些事儿
