Why std::binary_search on std::list Works in C++ STL ?

A common error made by beginning users of the Standard Library containers and algorithms in C++ is to write code whose run time complexity (big-O) is disaster.

In most cases, the Standard Library tries to keep us out of trouble by making it convenient to use algorithms in a really efficient way. But thanks to the great generality and power of the C++ templates used in the Standard Library, there are some loopholes that allow you to write hopelessly inefficient code as easily as very efficient code.

One such loophole is that you can easily write Standard Library code that does a binary search on a linked list, which is so ridiculously inefficient that saying “binary search on a linked list” is actually a geeky programming joke! Linked-lists are supposed to be searched linearly!

The Standard Library allows you to apply the binary_search and lower_bound algorithms to any sorted sequence container, including std::list, and it will produce a correct result.

The following works for any sequence container:

binary_search(container.begin(), container.end(), probe)

here probe is nothing but what operator you are looking for searching, by default it is equality.

a linked list has the property that the only way you can find a particular node is to start at one end of the list and follow the links from one node to the next, checking them one at a time. Unlike with array subscripting, there is no way to compute the location of a list node directly from its numerical position in the list — it could be anywhere in memory. So how is it that you can do a binary_search on a std::list?

The basic binary search algorithm involves calculating the midpoint of a range of values, and then checking the value at that midpoint. The code does this by calling std::distance, which returns the numerical distance between the first and last iterators. This distance is divided by two, and then std::advance is called to move the first iterator forward by that amount to get to the midpoint of the range. The distance and advance functions are also function templates that are defined so that they work with iterators into any type of container. Template magic is used to specialize them for different iterator types.

When these functions are applied to a built-in array or a std::vector container, the distance and advance functions
will compile down to simple subtraction and addition of the subscript values/pointers, taking almost no time. But if applied to a list, whose iterators support only moving forward or back by one step at a time, then the binary search will require using the distance function to repeatedly count the nodes between the ends of the narrowing range and then advance with increment and count again to position at the midpoint. Surely all this link-following will add up to a substantial amount of time!

The C++98 Standard in fact states that lower_bound and binary_search will run in O(log n) time when applied to a container with random access iterators. When applied to a container that lacks random-access iterators, like std::list, the Standard states that the search will be logarithmic with the number of comparisons, but linear with the number of nodes visited. So whether it runs faster than a linear search depends on how much time it takes to do the comparisons compared to counting the nodes over and over again.

So, for vector or deque advance function crops the search space to half every time to make the time complexity
O(log N) but in case of list, they do not really do crops out the search space to half every time and resulting in search complexity O(N), and which is more expensive than linear on vector due to pointers.

Conclusion:

Is there ever a reason to do a binary search of a linked list? Based on these results, the costs of the
comparison would have to be gigantic, much more than in this comparison, to even get into the running. You should only
consider it if for some reason you have to use a linked-list container. Even so, you should construct and run a relevant
benchmark to be sure. It certainly looks like doing a binary search on a linked list is a joke after all.

#happy_coding