0

I know Binary search works on sorted arrays as it is possible to access the middle element in unit time, due to array indexing. But in lists it would take linear time to access the middle element, making binary search pointless. Vectors have flexible size like lists so if they're implemented using lists,binary search shouldn't work on them right? Or do vectors use arrays with dynamic memory allocation and will binary search work in that case? (I'm a beginner so please point out any flaws in my logic)

Konrad Rudolph
  • 530,221
  • 131
  • 937
  • 1,214
naruto4526
  • 9
  • 2
  • 1
    How a vector is implemented(from user's perspective) is not as important as how it behaves. The standard mandates behavior not implementation. – Jason Sep 10 '22 at 07:28
  • 3
    A `std::vector` is a dynamically-sized array. [This](https://en.cppreference.com/w/cpp/container/vector) is a good site for looking things up. And [this book list](https://stackoverflow.com/questions/388242/the-definitive-c-book-guide-and-list) is another good resource. (If vectors were implemented as linked lists they would be pointless, since they would just be linked lists.) – molbdnilo Sep 10 '22 at 07:28
  • A vector is a kind of dynamic *array*. It's really just a wrapper around a heap-allocated array. Though not that it really matters, any indexable and "array-like" container could be used for binary search just like any actual array. – Some programmer dude Sep 10 '22 at 07:28
  • @naruto4526 std::vector has random access iterators. So the search will be efficient as with arrays. – Vlad from Moscow Sep 10 '22 at 07:28

1 Answers1

8

Vectors have flexible size like lists so if they're implemented using lists

Vectors cannot be implemented using linked lists. It is a requirement of std::vector that it has constant-time access by numeric index, and that the values are stored contiguously like an array. So binary search is perfectly fine, so long as the values are kept sorted.

John Zwinck
  • 239,568
  • 38
  • 324
  • 436