高中信息技术 浙教版选修1 5.4查找算法的程序实现(共20张PPT)

查找算法的程序实现 价格猜猜猜小游戏 课堂思考 问题一：你用什么方法猜出所有的价格,大概描述下?     问题二：怎么样能用尽量少的次数猜出三件商品的价格? （1）对分查找是效率很高的查找方法，但被查找的数据必须是有序的。 对分查找的原理和方法 （2）首先将查找的数与有序数组内处于中间位置的数据比较，如果中间位置上的数与查找的数不同，根据有序性，就可确定应该在数组的前半部分还是后半部分继续查找。 （3）在新确定的范围内，继续按上述方法进行查找，直到获得最终结果。 举 例 d(1) 22 d(2) 28 d(3) 30 d(4) 33 d(5) 38 d(6) 39 d(7) 41 d(8) 50 d(9) 55 d(10) 58 说明： 1、d（1 to 10）数组来存放一组升序序列数据； 2、i表示查找范围的第一个数组元素的下标； 3、j表示最后一个数组元素的下标； 4、mid表示中间位置元素的下标； 5、key保存要查找的数。 ← i ←mid=fix((i+j)/2) ← j 情况一：要找的值在后半部分，如要查找数key=55 ① 第一次查找 d(1)---d(10) key=55 则i=1; j=10; mid=fix((1+10)/2)（mid=5） d(1) 22 ← i d(2) 28 d(3) 30 d(4) 33 d(5) 38 ←mid=fix((i+j)/2) d(6) 39 d(7) 41 d(8) 50 d(9) 55 d(10) 58 ← j key>d(mid) 说明key在后半部分；i=mid+1 (i=6)； j不变。 Key>d(mid) ②第二次查找d(6)---d(10); key=55 i=6;j=10;mid=fix((6+10)/2)=8 d(1) 22 d(2) 28 d(3) 30 d(4) 33 d(5) 38 d(6) 39 ← i d(7) 41 d(8) 50 ←mid=fix((i+j)/2) d(9) 55 d(10) 58 ← j key>d(mid) 说明key在后半部分；i=mid+1（i=9）； j不变。 Key>d(mid) ③第