2 ms·
Can you do binary search without random access? I would not expect so. Am I missing a point that someone could explain?
by fn-mote 3y ago
Can you do binary search without random access? I would not expect so. Am I missing a point that someone could explain?
- andyg_blog 3y agoThe C++ standard measures the time complexity of lower_bound and binary_search by the number of comparisons performed. So yes, it's possible on e.g., a linked list like std::list (by this definition)
- kccqzy 3y agoObserve that you can restrict your code to only call std::advance on the iterator. So definitely you could do binary search without random access, and you would actually iterate over all elements, but you just skip the comparison function for the majority of elements.