解：
1 4 5 7 8 9 10 22 12 15 23 27 35 22 32 23 35 27 32 35
12 15
27 32
35
→i=14
时间复杂性
二分搜索算法的时间复杂性满足:
n 1 1 n T ( n) 1 T( ) n 1 2
二分搜索算法的时间复杂度为 O(log n)
算法设计1
对金块逐个的进行比较查找。先拿出两块比较重量， 留下重的一个与下一块进行比较，直到全部比较完 毕，就找到了最重的金子。
1
2
3
…
(n-1)
n
(2n-3)
(n-2)最轻
算法设计2
用分治法(二分法)可以用较少的比较次数解决上述问题。
…
…
…
…
在含 n 个元素的集合中寻找最大元素和最小元素。
1)将数据等分为两组，目的是分别选取其中的最大(小)元素；
分治过程：
n n n T (n) T ( ) T ( ) T ( k ) T (1) 2 4 2
练习：金块问题
老板有一袋金块（共 n 块， n 是 2 的幂 (n 2) ） ，最优秀的 雇员得到其中最重的一块，最差的雇员得到其中最轻的 一块。假设有一台比较重量的仪器，希望用最少的比较 次数找出最重和最轻的金块。
时间复杂性
算法分析:设 T (k ) 为覆盖 2 k 2 k 残缺棋盘的时间,
1) 2)
k 0 k 0
覆盖它需要常数时间O(1)
测试哪个子棋盘残缺以及形成3个残缺子棋盘需要O(1) 覆盖4个残缺子棋盘需四次递归调用,共需时间
4T (k 1)
算法的时间复杂性递推式为：
O(1) k 0 T (k ) 4T (k 1) O(1) k 0
作业
P38
2-3
是否能将问题分治为2个子问题？
2) 棋盘上有一个残缺方格
分解后的子问题中应该有一个残缺方格。
a) k=2时的棋盘
b）分解后
c)分治后
分治算法：
1) 当 k 0 时,将 2 k 2 k 棋盘分割为 4 个 2 k 1 2 k 1 子棋盘；
2k 1 2k 1
2k 1 2k 1
2)递归分解直到每组元素的个数，可以简单地找到
最大（小）元素； 3)回溯时合并子问题的解，在两个子问题的解中大者取大， 小者取小，即合并为当前问题的解。
时间复杂性满足递归关系式：
0 n 1 T ( n) 1 n2 2T ( n ) 2 n 2 2
解： (n) 2 k 1 T ( T
§2.6 棋盘覆盖
复习
1)分解：把原问题分解为若干个规模较小、相互独立， 与原问题相同的子问题，并尽量使这 k 个子问题的 规模大致相等； 2)求解 3)合并
问题
在一个 2k 2k 个方格组成的棋盘中,若恰有一残缺 方格（该方格与其它方格不同） （如下图） 。
图2-4 k=2时的一个特殊棋盘
解： (k ) 4T (k 1) O(1) T
4 k T (0) O(1) 4i 4 k O(1) O(1)( 4 k 1) / 3
i 0
k 1
T (k ) O(4 )
k
分治过程
n n n T (n) T ( ) T ( 2 ) T ( k ) T (1) 4 4 4
n 2
) 2i k 1
i 1
k 1
2
k 1
3 (2 2) n 2 2
k

算法的时间复杂性满足如下的递归关系式：
0 n 1 T ( n) 1 n2 n n T ( 2 ) T ( 2 ) 2 n 2
2k 1 2k 1 2k 1 2k 1
残缺方格必位于4个子棋盘之一其余3个子棋盘中无残缺方格。
2) 用一个L型骨牌覆盖这3个较小棋盘的结合处。
2k 1 2k 1
2k 1 2k 1
2k 1 2k 1 2k 1 2k 1
这3个子棋盘上被L型骨牌覆盖的方格就成为该棋盘上的残缺方 格,原问题转化为4个较小规模的棋盘覆盖问题。递归地使用这 种分割，直至棋盘简化为11棋盘。
棋盘覆盖问题：要求用4种不同形态的L型骨牌覆盖该棋盘上
除残缺方格外的所有方格且任何2个L型骨牌不得重叠覆盖。
(a)
(b)
(c)
(d)
** 2k 2k的棋盘覆盖中，用到的骨牌数为(4k-1)/3。
图2-4 k=2时的一个特殊棋盘
图2-4 覆盖后
对 2k 2k 的棋盘有如下的特点：
1)是正方形
二分搜索
amid
a1
x amid
…
…
an
x a mid
a1
…
…
an
二分搜索算法的基本思想
将 n 个元素分成个数大致相同的两半，取 amid 与 x 作比较。
1) x a mid 2)
算法终止 在数组的左半部继续搜索 在数组的右半部继续搜索
x a mid
3) x a mid
例2：设a=[1 4 5 7 8 9 10 12 15 22 23 27 32 35],搜索x=35。
§2.3 二分搜索技术
问题：
给定已按升序排好序的n个元素a[0:n-1]，现要在这n个
元素中找出一特定元素x。
例 1、设 n 6, a [1 3 5 6 7 9] ，要找出特定元素 x 9 。
顺序查找
1
3
5
6
7
9
用顺序搜索方法，逐个比较 a[0 : n 1] 中元素，直至找 出元素 x 或搜遍整个数组后确定 x 不在其中。 在最坏情况下，顺序搜索方法需要 O(n) 次比较。