二进制搜索在实践中使用在哪里？

每个程序员都被教导二进制搜索是一种搜索有序数据列表的好方法.有许多玩具教科书使用二进制搜索的例子,但在实际编程中呢:在现实生活中程序中实际使用的二元搜索在哪里？

二进制搜索随处可见.从任何语言库(Java,.NET,C++ STL等)获取任何已排序的集合,他们都将使用(或可以选择使用)二进制搜索来查找值.虽然你必须很少实现它,但你仍然必须理解它背后的原理才能利用它.

当内存空间紧张时,二进制搜索可用于快速访问有序数据.假设您要在可搜索的有序数据结构中存储一组100.000个32位整数,但您不会经常更改该集合.您可以将整数存储在400.000字节的排序数组中,并且可以使用二进制搜索快速访问它.但是如果你将它们放入B树,RB树或任何"更动态"的数据结构中,你就会开始产生内存开销.为了说明,将整数存储在您已经离开子指针和右子指针的任何类型的树中将使您消耗至少1.200.000字节的内存(假设32位内存架构).当然,你可以做一些优化,但这就是它的工作原理.

因为更新有序数组(执行插入或删除)非常慢,所以当数组经常更改时,二进制搜索没有用.

这里有一些我使用二进制搜索的实际例子:

在虚拟机中实现"switch()... case:"构造,其中案例标签是单个整数.如果您有100个案例,则可以使用二分搜索在6到7个步骤中找到正确的条目,其中条件分支序列平均需要进行50次比较.

使用后缀数组进行快速子串查找,后缀数组包含lexiographic排序中可搜索字符串集的所有后缀(我想节省内存并保持实现简单)

寻找方程的数值解(当你懒惰而不介意实现牛顿方法时)

每个程序员都需要知道在调试时如何使用二进制搜索.

当你有一个程序,并且你知道在程序执行期间某个特定点可以看到一个错误时,你可以使用二进制搜索来指出它实际发生的位置.这比单步执行大部分代码要快得多.

二进制搜索是一种快捷的方式!

在STL和.NET框架等到来之前,您经常遇到需要滚动自定义集合类的情况.每当排序的数组是存储数据的可行位置时,二进制搜索将是定位该数组中的条目的方式.

我非常确定二进制搜索现在也在广泛使用,尽管图书馆为了您的方便而对其进行了"引人注目".

我在BTree实现中实现了二进制搜索.

BTree搜索算法用于查找要读取的下一个节点块,但是在4K块本身(其中包含基于密钥大小的多个密钥)中,二进制搜索用于查找记录号(对于叶节点) )或下一个块(对于非叶节点).

与顺序搜索相比,速度快,因为与平衡二叉树一样,每次检查都会删除剩余搜索空间的一半.