变种

如果你希望支持“查找或者插入”操作，那么图5-2中第10行的ix最终值表示了缺失元素需要插入的索引值（所有较高的索引值都需要增加）。

二分查找有两个主要的变种。第一个和处理动态数据有关，在允许高效地插入或者删除时也需要维护一个可以接受的查找性能。如果集合是以数组的形式存储的话，因为每一个数组的条目都是一个有效的元素，所以插入和删除将会比较低效。因此，插入操作将会扩展这个数组（从逻辑上或者物理上）并且平均需要移动一半的元素。删除需要缩短数据并且也需要移动一半的元素。任何一个都是不可接受的。

如果集合能够存储在内存中，那么一个好的方法是使用基于散列，并且使用冲突链的查找。见下一节“基于散列的查找”，这个查找描述了查找动态数据的方法。一个替代的方法是在内存中构造一个二叉查找树。如果插入和删除操作是随机的，那么这个替代的方法实现起来非常简单，并且树不会偏置。但是，经验告诉我们这种情况很少发生，所以需要使用查找树的一个更复杂类型——平衡二叉树（Cormen等，2001）。

广告：个人专属 VPN，独立 IP，无限流量，多机房切换，还可以屏蔽广告和恶意软件，每月最低仅 5 美元

第二种变种处理的数据是动态的，并且由于过大不能存放在内存中。当这种情况发生时，查找时间就取决于二级存储器的输入输出操作所花费的时间。一个更有效的解决方法是使用叫做B树的n元树。这是一个多级树，并且在二级存储器上有较好的性能表现。在http://www.bluerwhite.org/btree上你能找到B树的教程，还包含一些例子。