《3.3 二分法查找及其应用》由会员分享，可在线阅读，更多相关《3.3 二分法查找及其应用（16页珍藏版）》请在金锄头文库上搜索。
1、猜价格 游戏规则首先由第一位同学确定商品价格，并告知该商品的价格范围(1100)，然后由另一位同学猜价格，如果猜中，则游戏结束，否则第一位同学告诉第二位同学“高了”还是“低了”，第二位同学继续猜，直至游戏结束。思考:游戏过程中，可以采用什么方法快速猜中价格？3.3二分法查找及其应用安徽省阜阳第一中学 杨艳平高中信息技术选修一算法与程序设计 使用场合二分法查找也叫对半查找，是一种为高效查找而设计的算法，一般用于数据量较大的序列的查找。 算法思想1、取中间值：取查找序列的中间元素；2、比较：中间元素与目标元素对比，若相等，代表找到；若目标元素较小，就在查找序列的前半部分继续查找，反之，则在查找序列
2、的后半部分继续查找；3、反复舍半查找，直至确定目标元素在查找序列中（或者确定不在）。 查找模拟21354687910字符说明L(ow)：下界H(igh)：上界M(iddle)：中间元素K(ey)：目标元素模拟操作演示模拟操作演示操作说明:先分别拖动“H”,“L”到某数字上确定查找上,下界，再拖动“K”到某数字下指定待查值，然后再根据二分法查找思想，不断拖动“M”,“L”,“H”图标到计算得到的数字上，直至查找结束。以上操作用于模拟使用二分法算法查找“K”指向数字的过程。下页MK字符说明L(ow)：下界H(igh)：上界M(iddle)：中间元素K(ey)：目标元素Y(es)：是N(o)：否 流
3、程图描述=YN操作要求:请根据二分法查找思想，将流程图下面的4个处理框拖放到流程图的合适位置。下页 程序实现小组各成员自主探究完成任务1：打开学生文件夹下打开学生文件夹下“工程工程1工程工程1.vbp”，先修改程序，先修改程序(L及及H的值的值)，再运行程序，依次输入指定范围，再运行程序，依次输入指定范围内的目标元素，分析每个目标元素的查找次数，再预测在该查找范内的目标元素，分析每个目标元素的查找次数，再预测在该查找范围内查找任意一个数的最大查找次数。组长汇总结果入表并评判。围内查找任意一个数的最大查找次数。组长汇总结果入表并评判。组别:查找范围查找范围:110目标元素2612最大次数评判(W
4、/R)记录次数查找范围查找范围:1100目标元素860101最大次数评判(W/R)记录次数 查找范围查找范围:201300目标元素203280301最大次数评判(W/R)记录次数 查找效率下页 课堂检测 课堂检测 算法变身 A(1) A(2) A(3) A(4) A(5)18730100A(1) = 1A(2) = 7A(3) = 8A(4) = 30A(5) = 100数组:一组相同类型的变量集合，集合中的每个变量都是独立的变量，他们通过数组序号被引用。Dim A(5) As Integer定义:思考思考:引用数组进行二分法查找时，与待查值引用数组进行二分法查找时，与待查值K比较的是比较的是
5、?LMHK=8中间值中间值M？序号为中间值的序号为中间值的数组元素数组元素A(M)？ = KKMMA(M) A(M) L=M+1 H=M-1 变身流程图YN组内成员合作完成任务2：打开学生文件夹下打开学生文件夹下“工程工程2工程工程2.vbp”，运行程序，输入待查值运行程序，输入待查值(如：如：8)，输入查找过程中依次查找的数，再评，输入查找过程中依次查找的数，再评判结果。组长汇总、汇报学习结果。判结果。组长汇总、汇报学习结果。查找数列待查值在数列中依次查找的数评判结果(W/R)836100 变身演练（1）二分法查找：优点是减少了查找的次数，提高了查找效率。缺点是必须是在有序数列中才能使用，算法有难度。（2）顺序查找：优点是算法简单，对查找数列无任何要求。缺点是查找效率低，当数列中数据个数较多时不宜采用该方法查找。对比二分法查找与顺序查找算法，总结二分法查找算法的优缺点及适用场合。 学习总结（2）查找按字符排序的序列y=lnx+2x-6（1）求方程的近似解 拓展应用
