5.4 数据查找——二分查找 课件(共14张PPT) 2023—2024学年浙教版（2019）高中信息技术选修1

(课件网) 二分查找 Key 与中间位置的数比 比中间数小 比中间数大 二分查找思想 如：用数组d存放升序的数字序列 i表示查找范围第一个数组元素下标（起始位置） j表示查找范围最后一个数组元素下标（终止位置） m表示查找范围内中间位置数组元素的下标（中间位置） m=(i+j)//2 m =(i+j+1)//2 每次d[m]与Key比较会确定下一次查找范围 右半区间： 左半区间： i=m+1 j=m-1 d[m]key 二分查找思想 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 10 15 17 18 22 27 35 45 48 52 65 67 72 85 97 98 Key=52 ①变量 i和j记录所要查找范围的起始和终止位置 i=0 j=15 ②计算中间点M的位置：M= (i+j)//2 M= (i+j)//2 ③比较key和d(M)的值，根据结果重新确定查找的起始和终止位置或者直接告诉已经找到 第1次比较：Key>d[m] 查找范围：d[8]~d[15] j不变，i=M+1=8 i=8 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 10 15 17 18 22 27 35 45 48 52 65 67 72 85 97 98 M=(i+j)//2 第2次比较：Key>d[m] 查找范围：d[8]~d[10] i不变，j=M-1 j=10 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 10 15 17 18 22 27 35 45 48 52 65 67 72 85 97 98 第3次比较： Key=d[m] 找到了！ M= (i+j)//2 二分查找思想 二分查找程序实现 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 10 15 17 18 22 27 35 45 48 52 65 67 72 85 97 98 查找次数 搜索区间 中点 查找键与中点关系 i j 0 15 第一次 d[0]~d[15] 7 key>d[m] 8 15 第二次 d[8]~d[15] 11 keyd[m] 8 15 第二次 d[8]~d[15] 11 keyd[m] 10 10 第四次 d[10]~d[10] 10 key