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)
1 Answers
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.
Related