哪个算法简单到初学编程的人都能轻松实现,但有多年编程经验的人也可能会写出严重的 bug 呢?没错,正是二分查找。既然普通人的二分查找容易写错,那专业人士会如何实现二分查找呢?不妨参考一下 clang 7.0 的实现。
lower_bound
是指在区间 [first, last)
中,对于任意 i < j
,若 comp(A[i])
为真,则 comp(A[j])
必为真。如下图
让我们看一看 lower_bound 的实现
__lower_bound(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_, _Compare __comp)
{
typedef typename iterator_traits<_ForwardIterator>::difference_type difference_type;
difference_type __len = _VSTD::distance(__first, __last);
while (__len != 0)
{
difference_type __l2 = __len / 2;
_ForwardIterator __m = __first;
_VSTD::advance(__m, __l2);
if (__comp(*__m, __value_))
{
__first = ++__m;
__len -= __l2 + 1;
}
else
__len = __l2;
}
return __first;
}
// This file is dual licensed under the MIT and the UIUC license.
代码很精简,不到十行,注意几个关键点就不会写错
- 定义:
first
是第一个有可能为真的元素 - 迭代:
l2 < len
恒成立,因此first+l2
就不会越界。同时,每次迭代时len
严格递减 - 迭代结束:
l2 == 0
当且仅当len == 1
。这是我们最后一次进行迭代 - 特殊情况:如果所有的元素都为假,那最后一次迭代时,
++m
的结果正是last
相比我之前写的不时丢弃真值、出现死循环的二分查找,clang 的代码可是高到不知道哪里去了。
upper_bound 的实现 看起来是相反的,不过从布尔值的角度看,与 lower_bound
是一样的,我就不复制代码了。
上文中的示意图使用 R 语言绘制,参考了 Stack Overflow 上画棋盘的讨论。代码如下
b <- matrix(nrow=1,ncol=6)
colorindex <- c(rep(0, 4), rep(1, 2))
# for each square
colors <- c("red", "green")[colorindex+1] # choose colors
side <- 1/8 # side of one square
ux <- col(b)*side # upper x values
lx <- ux-side # lower x values
uy <- row(b)*side # upper y
ly <- uy-side # upper y
plot.new() # initialize R graphics
rect(lx, ly, ux, uy, col=colors, asp=1) # draw the board
最后,按照惯例推荐一本书 Effective C++:改善程序与设计的55个具体做法(第3版)