对分查找复习公开课PPT课件

1、12用一个数组用一个数组d(1)d(11)d(1)d(11)来存放来存放升序升序的元素序列，的元素序列，查找键查找键keykey为为1212。d(1) d(2) d(3) d(4) d(5) d(6) d(7) d(8) d(9) d(10) d(11)6 612121515181822222525282835354646585860603mid第三次查找：第三次查找：12345678910116 61212 1515 1818 2222 2525 2828 3535 464658586060开始开始ijmid第一次查找：第一次查找：第二次查找：第二次查找：midjjimid第四次查找：第四次

2、查找：4流程图未找到，输出结果：未找到，输出结果：0开始开始i1 ，jni=j?找到，输出结果：找到，输出结果：m结束结束ny计算中点计算中点m (i+j)2d(m)=key?d(m)key?im+1jm-1yynn51.71.7个学生的身高（单位个学生的身高（单位cmcm）从高到低依次为：）从高到低依次为：178,177,175,172,170,165,162178,177,175,172,170,165,162。用对分查找找到。用对分查找找到178178的过程中，依次被访问到的数据是的过程中，依次被访问到的数据是：（：（ ）a.178 b. 172,175,178a.178 b. 172,

3、175,178c. 172,177,178 d.172,175,177,178c. 172,177,178 d.172,175,177,1786若有若有10241024个数据，个数据，顺序查找最多查找次数为？顺序查找最多查找次数为？对分查找对分查找最多查找次数为？最多查找次数为？i=1 j=10241.5122.2563.1284.645.326.167.88.49.210.11.5122.7683.8964.9605.9926.10087.10168.10249.102210.102311.1024最多进行最多进行log2n+1次次72. 2.编写编写vbvb程序，实现如下功能：产生程序，实

4、现如下功能：产生1010个个随机数升序排列在随机数升序排列在list1list1中，在中，在text1text1中输中输入一个正整数入一个正整数key,key,单击单击“查找查找”按钮，按钮，用对分查找的思想在用对分查找的思想在label2label2中显示查找结中显示查找结果。果。8（1）前提：被查找的数据序列必须）前提：被查找的数据序列必须 有序有序（2）基本思想：）基本思想： 在有序的数据序列中（一般放在数组中），首先把在有序的数据序列中（一般放在数组中），首先把查找的数据与数组查找的数据与数组中间位置中间位置的元素进行比较，的元素进行比较，若相等若相等，则查找成功并退出查找；则查找成功并退出查找；否则，根据数组元素的有序性否则，根据数组元素的有序性，确定数据应在数组的前半部分还是在后半部分查找；重确定数据应在数组的前半部分还是在后半部分查找；重复进行以上比较，直到找到或未找到为止。