首页 » 算法技术手册 » 算法技术手册全文在线阅读

《算法技术手册》变种

关灯直达底部

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

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

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

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