How std::binary_search work with std::list?

The C++ Standard Library provides a variety of algorithms which coupled with their generality, make them greater alternate over user-defined code which might not be efficient. The advantage of the Standard Library algorithm is not only the freedom of containers choice for the user but also the flexibility it offers via predicates. But in few cases depending upon the choice of container, certain Standard Library algorithms may not work. For example, std::list container can not be used along with std::sort algorithm as iterator required by std::sort should support random access.

The basic binary search algorithm involves calculating the midpoint of a range of values or containers and then checking the value at that midpoint. Since std::list does not support random access iterator, then how does the std::binary_search algorithm work with std::list? The only way to access a node or link of std::list is to traverse one link at a time till we reach desired link location. Hence we can ask, how the std::binary_search algorithm works perfectly well with std::list?

To solve the ugly traversal through std::list, the Standard Library of C++ relies on the template magic of std::distance and std::advance. For example, to calculate the midpoint in std::list, Standard Library uses std::distance which returns the numerical distance between the first and the last iterator. This distance is then divided by two to get the midpoint in the std::list and then std::advance is called to move the iterator forward by that amount to get to the midpoint range.

The advantage of this approach is the std::distance and std::advance are function templates and they are defined to work with any type of container iterator. Let's try to implement our own binary search for std::list to understand this concept better.

// binary search for list<string>
#include<iostream>
#include<list>
#include<vector>
#include<string>
#include<iterator>     // used for implementing binary sort for list

using namespace std;

bool binary_search_list(list<string>::iterator first, list<string>::iterator last, string val)
{
  list<string>::iterator middle;
  iterator_traits<list<string>::iterator>::difference_type count, step;
  count= distance(first, last);
  
  while(count>0)
  {
    middle= first;
    step=count/2;
    advance(middle, step);
    if(*middle==val)
      return true;
    else if(*middle<val)
    {
      advance(middle, 1);
      first=middle;
    }
    else
    {
      advance(middle, -1);
      last=middle;
    }
    count= distance(first, last);
  }
  return false;
}

int main()
{
  
  list<string> fruits{"apple","banana","kiwi", 
  "pineapple","guava","orange",
  "dragon fruit","mango","chicoo","watermelon"};
  
  fruits.sort();   // binary search pre-requisit
  
  cout<<"Printing sorted list of fruits:\n";
  for(auto fruit: fruits)
    cout<<fruit<<",\t";
  cout<<endl;
  
  string str_pattern="watermelon";
  
  auto result=binary_search_list(fruits.begin(), fruits.end(),str_pattern);
  if(result)
    cout<<str_pattern<<" is present in list\n";
  else
    cout<<str_pattern<<" is not present in list\n";
    
  return 0;
}

Output:

Printing sorted list of fruits:
apple, banana, chicoo, dragon fruit, guava, kiwi, mango, orange, pineapple, watermelon, 
watermelon is present in list

Conclusion

As we have seen the Standard Library contains a rich collection of templated containers and algorithms which makes the task of solving many problems simpler. Understanding how STL containers and the algorithms are implemented gives us insight into how to write efficient and defect-free code.