问题
在长度为n n n 的升序(从小到大)序列s s s 中查找元素x x x 的位置。
解法
令l o w = 0 , h i g h = n − 1 , m i d = ⌊ l o w + h i g h 2 ⌋ low = 0, high = n-1, mid = \lfloor \frac{low+high}{2} \rfloor l o w = 0 , hi g h = n − 1 , mi d = ⌊ 2 l o w + hi g h ⌋ ,元素x x x 与m i d mid mi d 的关系有三种情况:
(1) 若x = s [ m i d ] x = s[mid] x = s [ mi d ] ,显然已经查询到元素x x x 的位置,算法结束;
(2) 若x < s [ m i d ] x \lt s[mid] x < s [ mi d ] ,则x x x 处于s [ m i d ] s[mid] s [ mi d ] 左边;
(3) 若x > s [ m i d ] x \gt s[mid] x > s [ mi d ] ,则x x x 处于s [ m i d ] s[mid] s [ mi d ] 右边;
该操作用伪代码表示为:
Copy function Search(s, low, high, x):
let mid = (low + high) / 2
if x = s[mid]
return true, mid
else if x < s[mid]
return false, low, mid-1
else if x > s[mid]
return false, mid+1, high
(1) Search函数第2行:计算搜索范围的中间位置m i d mid mi d ,以s [ m i d ] s[mid] s [ mi d ] 为基准与x x x 进行比较;
(2) Search函数第3-8行:比较s [ m i d ] s[mid] s [ mi d ] 和x x x ,若x = s [ m i d ] x = s[mid] x = s [ mi d ] 则找到结果,若x < s [ m i d ] x \lt s[mid] x < s [ mi d ] 则在s [ l o w , m i d − 1 ] s[low, mid-1] s [ l o w , mi d − 1 ] 继续寻找,若x > s [ m i d ] x \gt s[mid] x > s [ mi d ] 则在s [ m i d + 1 , h i g h ] s[mid+1, high] s [ mi d + 1 , hi g h ] 继续寻找;
上述操作,可以用下图中的示例:
若x = 17 = s [ m i d ] x = 17 = s[mid] x = 17 = s [ mi d ] ,可以直接找到x = s [ 4 ] x = s[4] x = s [ 4 ] :
若x = 5 < s [ m i d ] = 17 x = 5 \lt s[mid] = 17 x = 5 < s [ mi d ] = 17 ,则令h i g h = 3 high = 3 hi g h = 3 之后继续搜索:
若x = 30 > s [ m i d ] = 17 x = 30 \gt s[mid] = 17 x = 30 > s [ mi d ] = 17 ,则令l o w = 5 low = 5 l o w = 5 之后继续搜索:
外围只需循环调用Search函数即可:
Copy function BinarySearch(s, n, x):
let low = 0, high = n-1
while low <= high
let found, low, high = Search(s, low, high, x)
if found
return low
return -1
复杂度
Search函数的输入规模为T ( 4 ) T(4) T ( 4 ) ,该函数中最多有1次加法、1次除法、3次比较操作,因此时间复杂度为
T ( 4 ) = O ( 5 ) = O ( 1 ) T(4) = O(5) = O(1) T ( 4 ) = O ( 5 ) = O ( 1 ) BinarySearch函数的输入规模为T ( n ) T(n) T ( n ) ,每次调用Search函数后h i g h − l o w high - low hi g h − l o w 的值都会减小一半,即
T ( n ) = T ( n 2 ) + O ( 1 ) = T ( n 2 2 ) + 2 ⋅ O ( 1 ) = T ( n 2 3 ) + 3 ⋅ O ( 1 ) = ⋯ \begin{matrix}
T(n) & = & T(\frac{n}{2}) + O(1) \\
& = & T(\frac{n}{2^2}) + 2 \cdot O(1) \\
& = & T(\frac{n}{2^3}) + 3 \cdot O(1) \\
& = & \cdots
\end{matrix} T ( n ) = = = = T ( 2 n ) + O ( 1 ) T ( 2 2 n ) + 2 ⋅ O ( 1 ) T ( 2 3 n ) + 3 ⋅ O ( 1 ) ⋯ 假设递归层数为L L L ,可得:
T ( n 2 L ) = 1 T(\frac{n}{2^L}) = 1 T ( 2 L n ) = 1 即:
L = T ( l o g 2 n ) = O ( l o g 2 n ) L = T(log_2 n) = O(log_2 n) L = T ( l o g 2 n ) = O ( l o g 2 n ) 将L L L 代入原始递推公式,可得:
T ( n ) = T ( n 2 L ) + L ⋅ O ( 1 ) = O ( 1 ) + O ( l o g 2 n ) ⋅ O ( 1 ) = O ( l o g 2 n ) \begin{matrix}
T(n) & = & T(\frac{n}{2^L}) + L \cdot O(1) \\
& = & O(1) + O(log_2 n) \cdot O(1) \\
& = & O(log_2 n)
\end{matrix} T ( n ) = = = T ( 2 L n ) + L ⋅ O ( 1 ) O ( 1 ) + O ( l o g 2 n ) ⋅ O ( 1 ) O ( l o g 2 n ) 该算法时间复杂度为O ( l o g 2 n ) O(log_2 n) O ( l o g 2 n ) ,空间复杂度为O ( 1 ) O(1) O ( 1 ) 。
源码
BinarySearch.h
BinarySearch.cpp
测试
BinarySearchTest.cpp