c++ - Dynamic ArrayList 的线性和二进制搜索

Question

嘿，我正在做一个动态数组列表，我想知道如何对数组列表进行线性和二进制搜索，以及这些搜索的优缺点是什么。

Answer 1

猜测您正在将这些实现为扩展数组，因为当您用完空间时，您会重新分配新数组，然后将元素复制过来。

在这种情况下，您的问题归结为如何在该数组上实现线性和二进制搜索？

在这种情况下，网上有很多文章、样本。

线性搜索的优势在于，对于小型数组，速度没有差异，只要您要查找的项目在数组中，它就会始终在未排序的数组上工作。

这与二分查找相反，二分查找对于大型数组非常快，但对于小型数组，与线性查找相比并没有真正的性能优势。这种加速的代价是必须对其进行排序才能获得这种优势。