1
第
第
6
6
章 分 治
章 分 治
3
6.1
6.1
引言
引言
例（找出伪币）
例（找出伪币）
给你一个装有
给你一个装有
16
16
个硬币的袋子，
个硬币的袋子，
16
16
个硬币中有一个
个硬币中有一个
是伪币，这个伪币要比真币轻一些。提供一台可用来比
是伪币，这个伪币要比真币轻一些。提供一台可用来比
较二组硬币重量的仪器，用它来找出伪币。
较二组硬币重量的仪器，用它来找出伪币。
方案一（逐一比较）
方案一（逐一比较）
比较硬币
比较硬币
1
1
和硬币
和硬币
2
2
，若不等，轻者则为伪币；否
，若不等，轻者则为伪币；否
则继续比较；
则继续比较；
比较硬币
比较硬币
1
1
和硬币
和硬币
3
3
，若不等，轻者则为伪币；否
，若不等，轻者则为伪币；否
则继续比较；
则继续比较；
按照这种方式，找出伪币最多需
按照这种方式，找出伪币最多需
15
15
次比较
次比较
(16-1=15)
(16-1=15)
最少仅为
最少仅为
1
1
次，平均
次，平均
8
8
次
次
。
。
算法时间复杂性可以用Ｏ
算法时间复杂性可以用Ｏ
(n)
(n)
来表示。
来表示。
4
方案二（采用分治法）
方案二（采用分治法）
将
将
16
16
个硬币问题划分为二个
个硬币问题划分为二个
8
8
个硬币的问题（
个硬币的问题（
A
A
组
组
和
和
B
B
组）。比较
组）。比较
A
A
和
和
B
B
，轻者含有伪币，假设
，轻者含有伪币，假设
B
B
较轻。
较轻。
将
将
8
8
个硬币的问题进一步划分为二个
个硬币的问题进一步划分为二个
4
4
个硬币的问题
个硬币的问题
（
（
B
B
1
1
组和
组和
B
B
2
2
组）。比较
组）。比较
B
B
1
1
和
和
B
B
2
2
，轻者含有伪币，假
，轻者含有伪币，假
设
设
B
B
1
1
较轻。
较轻。
将
将
4
4
个硬币的问题进一步划分为二个
个硬币的问题进一步划分为二个
2
2
个硬币的问题
个硬币的问题
（
（
B
B
11
11
组和
组和
B
B
12
12
组）。比较
组）。比较
B
B
11
11
和
和
B
B
12
12
，轻者含有伪币，
，轻者含有伪币，
假设
假设
B
B
12
12
较轻。
较轻。
因
因
B
B
12
12
只有
只有
2
2
个硬币，比较
个硬币，比较
2
2
个硬币就可找出伪币。
个硬币就可找出伪币。
找出伪币总的比较次数恒定为
找出伪币总的比较次数恒定为
4
4
（
（
log
log
2
2
16=4
16=4
）
）
。算
。算
法的时间复杂性可以用
法的时间复杂性可以用
Θ
Θ
(log
(log
2
2
n)
n)
来表示
来表示
。
。
5
6.2
6.2
二分搜索法
二分搜索法
给定元素
给定元素
x
x
和元素已按升序排列的数组
和元素已按升序排列的数组
A[low..high]
A[low..high]
，将
，将
x
x
与中间元素
与中间元素
A[mid]
A[mid]
作比较，
作比较，
其中
其中
mid=
mid=
(low+high)/2
(low+high)/2
。
。
如果
如果
x=A[mid]
x=A[mid]
，
，
则返回
则返回
mid
mid
。
。
如果
如果
x<A[mid]
x<A[mid]
，
，
则不考虑
则不考虑
A[mid..high]
A[mid..high]
，
，
对
对
A[low..mid-1]
A[low..mid-1]
重复实施相同的方法。
重复实施相同的方法。
如果
如果
x>A[mid]
x>A[mid]
，
，
则不考虑
则不考虑
A[low..mid]
A[low..mid]
，
，
对
对
A[mid+1..high]
A[mid+1..high]
重复实施相同的方法。
重复实施相同的方法。
由此启示，可用递归算法
由此启示，可用递归算法
BinarySearchRec
BinarySearchRec
来
来
实现二分搜索。
实现二分搜索。
