Open Liam0205 opened 5 years ago
https://liam.page/2018/11/23/binary-search-and-its-variants/
在前作讨论基于比较的排序算法的复杂度下界时,我们提及了二分搜索算法。 二分搜索是一个效率很高的算法。一个良好实现的二分搜索算法,其时间复杂度可以达到 $\Theta(\log n)$,而空间复杂度只有 $O(1)$。特别地,二分搜索算法的描述十分简洁。作为程序员,总是喜欢 clean and powerful 的东西。因此,二分搜索无疑对程序员有巨大的吸引力。 按照 Knuth 的说法,「尽管第一
https://liam.page/2018/11/23/binary-search-and-its-variants/
在前作讨论基于比较的排序算法的复杂度下界时,我们提及了二分搜索算法。 二分搜索是一个效率很高的算法。一个良好实现的二分搜索算法,其时间复杂度可以达到 $\Theta(\log n)$,而空间复杂度只有 $O(1)$。特别地,二分搜索算法的描述十分简洁。作为程序员,总是喜欢 clean and powerful 的东西。因此,二分搜索无疑对程序员有巨大的吸引力。 按照 Knuth 的说法,「尽管第一