山东省日照青山学校教科版高中信息技术课件+教案：选修一 3.3.3二分查找算法及程序实现 (2份打包)

---猜商品价格 * ￥5288 手机类型 4G手机，3G手机，智能手机，音乐手机，拍照手机 触摸屏类型 电容屏，多点触控 主屏尺寸 4.7英寸 主屏材质 Multi‑Touch（IPS技术） 主屏分辨率 1334x750像素 屏幕像素密度 326ppi 窄边框 4.25mm 屏幕占比 65.81% 二分查找的原理和方法 （1）二分查找是效率很高的查找方法，但被查找的数据必须是有序的。 （2）首先将查找的数与有序数组内处于中间位置的数据比较，如果中间位置上的数与查找的数不同，根据有序性，就可确定应该在数组的前半部分还是后半部分继续查找。 （3）在新确定的范围内，继续按上述方法进行查找，直到获得最终结果。 以规模为16的升序数组d为例：用一个数组d（1 to 16）来存放序列。 d(1) 10 d(2) 15 d(3) 17 d(4) 18 d(5) 22 d(6) 27 d(7) 35 d(8) 45 d(9) 48 d(10) 52 d(11) 65 d(12) 67 d(13) 72 d(14) 85 d(15) 97 d(16) 98 以规模为16的升序数组d为例：用一个数组d（1 to 16）来存放序列。 d(1) 10 d(2) 15 d(3) 17 d(4) 18 d(5) 22 d(6) 27 d(7) 35 d(8) 45 d(9) 48 d(10) 52 d(11) 65 d(12) 67 d(13) 72 d(14) 85 d(15) 97 d(16) 98 用i表示查找范围的第一个数组元素的下标，j表示最后一个数组元素的下标，m 表示中间位置元素的下标。 d(1) 10 d(2) 15 d(3) 17 d(4) 18 d(5) 22 d(6) 27 d(7) 35 d(8) 45 d(9) 48 d(10) 52 d(11) 65 d(12) 67 d(13) 72 d(14) 85 d(15) 97 d(16) 98 m=(i+j)\2 i j （1）第一种情况：要找的值在后半部分 以查找键Key=85为例,第一次查找:范围d(1)～d(16) d(1) 10 d(2) 15 d(3) 17 d(4) 18 d(5) 22 d(6) 27 d(7) 35 d(8) 45 d(9) 48 d(10) 52 d(11) 65 d(12) 67 d(13) 72 d(14) 85 d(15) 97 d(16) 98 i j m= (1+16)\2 （1）第一种情况：要找的值在后半部分 以查找键Key=85为例,第一次查找:范围d(1)～d(16) 比较后i=m+1 d(m)<Key所以可以确定接下来要找的范围是后半部分。 d(1) 10 d(2) 15 d(3) 17 d(4) 18 d(5) 22 d(6) 27 d(7) 35 d(8) 45 d(9) 48 d(10) 52 d(11) 65 d(12) 67 d(13) 72 d(14) 85 d(15) 97 d(16) 98 m=(1+16)\2 i j 第二次查找：范围d(9)～d(16), d(1) 10 d(2) 15 d(3) 17 d(4) 18 d(5) 22 d(6) 27 d(7) 35 d(8) 45 d(9) 48 d(10) 52 d(11) 65 d(12) 67 d(13) 72 d(14) 85 d(15) 97 d(16) 98 i j m=(9+16)\2 第二次查找：范围d(9)～d(16), 比较后：i=m+1 d(m)<Key 所以可以确定接下来要找的范围是后半部分。 d(1) 10 d(2) 15 d(3) 17 d(4) 18 d(5) 22 d(6) 27 d(7) 35 d(8) 45 d(9) 48 d(10) 52 d(11) 65 d(12) 67 d(13) 72 d(14) 85 d(15) 97 d(16) 98 m=(9+16)\2 i j 第三次比较：范围d(13)～d(16) d(1) 10 d(2) 15 d(3) 17 d(4) 18 d(5) 22 d(6) 27 d(7) 35 d(8) 45 d(9) 48 d(10) 52 d(11) 65 d(12) 67 d(13) 72 d(14) 85