Can we apply binary search on c++ list and vector?

Question

Binary search algorithm on c++ list and vector.
How can we do that? is there any restrictions?
please help.

Answer 1

It seems the built-in binary_search function in <algorithm> works on lists.

Thus, you may declare a similar binary_search function based on the one from <algorithm>

You can find details on it here :
www.cplusplus.com/reference/algorithm/binary_search
en.cppreference.com/w/cpp/algorithm/binary_search

https://code.sololearn.com/cGvcTDlqNa6s/?ref=app

Answer 2

I'm fairly sure that unlike vector, list does not provide random access, which means that you have to iterate through the list to get an item.

vec[5] // sixth element
list[5] // nope

This means that you can apply binary search on vector, given that the vector is sorted.

https://www.sololearn.com/learn/683/?ref=app
https://www.sololearn.com/learn/261/?ref=app

Answer 3

Aha, there's the catch.

https://stackoverflow.com/questions/14320395/binary-search-in-a-sorted-list-with-all-nodes-as-struct-c

It "works", but doesn't really carry out binary search on std::list the way you would expect it to.

Nonetheless, interesting discovery. Kinshuk Vasisht

Answer 4

Hatsy Rei Thank you!!!

Answer 5

Kinshuk Vasisht Thanks