算法技术手册 – 查找 – 二分查找

二分查找,要求集合是有序的,在这个条件基础上,它比顺序查找具有更好的性能。

如果使用伴随数组,只需要struct中有一个key是有序的就行。

需要指出的是,当数组放在磁盘上时,时间复杂度就不再是O(LogN),而取决于磁盘存取的开销。

源代码:

二分查找的变种:

1、支持快速插入和删除:由于原始集合是有序的,插入、删除都需要移动平均一半的数组。衍生出散列查找和平衡二叉树。

2、支持磁盘I/O:当数组存在磁盘上时,查找时间取决于磁盘操作所花费的时间。一个有效的方法是B树。

Leave a Reply

Your email address will not be published.