向量上可以进行二分查找吗？

Question

我知道二分搜索适用于排序数组，因为由于数组索引，可以在单位时间内访问中间元素。但在列表中，访问中间元素需要线性时间，使得二分搜索毫无意义。向量具有像列表一样灵活的大小，因此如果使用列表实现它们，则二分搜索不应该对它们起作用，对吗？或者向量是否使用具有动态内存分配的数组，并且在这种情况下二分搜索是否有效？（我是个初学者，逻辑上的错误还请大家指出）

Answer 1

向量具有像列表一样灵活的大小，因此如果它们使用列表来实现

向量不能使用链表来实现。要求std::vector它能够通过数字索引进行恒定时间访问，并且值像数组一样连续存储。因此，只要值保持排序，二分搜索就完全没问题。