资源简介

(共14张PPT)
二分查找
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]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 key第三次 d[8]~d[10] 9 key=d[m]
Key=52
二分查找程序实现
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 key第三次 d[8]~d[10] 9 key>d[m] 10 10
第四次 d[10]~d[10] 10 keyKey=55
二分查找程序实现
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=55
二分查找程序实现
二分查找程序实现
1 2 3 4 5 6 7 8 9 10
m=(i+j)//2
m =(i+j+1)//2
二分查找程序实现
1 2 3 4 5 6 7 8 9 10
m=(i+j)//2
m =(i+j+1)//2
二分查找练习
数组元素a[0]到a[7]的值分别是“11 ,22,33 ,44,55, 66,77, 88”。若该程序运行结束后，cs的值为2,则key可能的值是( )
A.33或77
B.22或66
C.22或77
D.33或66
B
二分查找练习
D
二分查找练习
B
二分查找练习
B

展开更多......

收起↑