近日被邀请在知乎上回答问题。鉴于这个问题已经被答烂了,所以将其存档在博客,以供后享。
谈谈二分搜索及其变体
在前作讨论基于比较的排序算法的复杂度下界时,我们提及了二分搜索算法。
二分搜索是一个效率很高的算法。一个良好实现的二分搜索算法,其时间复杂度可以达到 $\Theta(\log n)$,而空间复杂度只有 $O(1)$。特别地,二分搜索算法的描述十分简洁。作为程序员,总是喜欢 clean and powerful 的东西。因此,二分搜索无疑对程序员有巨大的吸引力。
按照 Knuth 的说法,「尽管第一个二分搜索算法早在1946年就被发表,但第一个没有bug的二分搜索算法却是在12年后才被发表出来」。
此篇我们讨论二分搜索算法的原理及其各种变体的实现。
Windows 上的 GIF 动画录像机和浏览器
在 Windows 7 的锁屏界面上执行命令/程序
更换 Windows 7 锁屏界面的背景
Windows 7 在登录时默认的背景图片是一片蓝色。作为一个程序员,我会倾向于认为,这片蓝色是一张图片资源。因此,它是可以被更换的。
这篇介绍如何更换 Windows 7 锁屏界面的背景。