4.3非数值计算（第一课时） (1) 课件 2021—2022学年教科版（2019）高中信息技术必修1

高一年级—教科版—信息技术—第四单元 4.3非数值计算 ----分治策略与二分查找 一、分治策略 分治的设计思想，是将一个难以直接解决的大问题，分割成一些较小的同类问题，各个击破， 最终达到解决问题的目的。 2 8 =23×23×22 =8×8×4 =256 二、二分查找 Ø 待查序列是有序的 以待查序列中点位置元素作为比较对象 如果小于中点位置元素，则将待查序列缩小为左半部分，否则为右半部分。 把待查序列一分为二进行判断，如此周而复始，直到找出这个数。 ....... ....... ....... ....... ....... ....... ....... ....... ....... ....... ....... flag_left flag_right 以递增数列为例 编写二分查找程序 编程练习： X是一个100以内的正整数，请你使用二分查找编程找出X ....... ....... ....... ....... ....... ....... ....... ....... ....... ....... ....... ....... ....... ....... ....... ....... ....... ....... ....... ....... ....... ...... ....... ....... ....... ....... ....... ....... ....... ....... ....... ....... mid=(flag_left+flag_right)//2 flag_left flag_right mid=(flag_left+flag_right)//2 flag_left flag_right 如果 x>mid: 待查序列在中点位置元素的右边待查序列为(mid+1,flag_right) if x>mid: flag_left=mid+1 以递增数列为例 ....... ....... ....... ....... ....... ....... ....... ....... ....... ....... ....... ...... ....... ....... ....... ....... ....... ....... ....... ....... .......