查找算法的程序实现 价格猜猜猜小游戏 课堂思考 问题一：你用什么方法猜出所有的价格,大概描述下? ? ? 问题二：怎么样能用尽量少的次数猜出三件商品的价格? （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) ③第三次查找d(9)--d(10) key=55 i=9;j=10;mid=fix((9+10)/2) ( mid=9) 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 ← i ←mid=fix((i+j)/2) d(10) 58 ← j key=d(mid) 说明找到了。 总结一：如果key>d(mid) ，新查找的范围为下半部分， j值不变，i=mid+1。 Key=d(mid) 情况二：要找的值在前半部分，如要查找数key=28 ① 第一次查找d(1)--d(10) key=28 i=1;j=10;mid=fix((1+10)/2)=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 keyd(mid) ③第三次查找 key =29 d (3)--d (4) i=3;j=4;mid=fix((3+4)/2)=3; d(1) 22 d(2) 28 d(3) 30 ← i ←mid=fix((i+j)/2) d(4) 33 ← j d(5) 38 d(6) 39 d(7) 41 d(8) 50 d(9) 55 d(10) 58 说明key在前半部分；j=mid-1(j=3) 。 Key
~~ 您好，已阅读到文档的结尾了 ~~
