Return true if value is in the range [ first ... last ). The first version assumes that the elements in [ first ... last ) are already sorted using operator< , whereas the second version assumes that the elements are already sorted using the comparison function compare .

Declaration


  
#include <algorithm>

template< class ForwardIterator, class T >
bool binary_search
  (
  ForwardIterator first,
  ForwardIterator last,
  const T& value
  );

template< class ForwardIterator, class T, class Compare >
bool binary_search
  (
  ForwardIterator first,
  ForwardIterator last,
  const T& value,
  Compare compare
  );

Complexity

Time complexity is O(log(N)) for random access iterators and O(N) for all other iterators. Space complexity is constant.

Example <ospace/osstd/examples/binsrch1.cpp>


    #include <iostream>
#include <algorithm>
#include <vector>

void
main()
  {
  int vector[ 100 ];
  for ( int i = 0; i < 100; ++i )
    vector[ i ] = i;
  if ( binary_search( vector, vector + 100, 42 ) )
    cout << "found 42\n";
  else
    cout << "did not find 42\n";
  }

found 42

Example <ospace/osstd/examples/binsrch2.cpp>


    #include <iostream>
#include <string.h>
#include <algorithm>
#include <vector>

bool str_compare( const char* a_, const char* b_ )
  {
  return ::strcmp( a_, b_ ) < 0 ? 1 : 0;
  }

const char* labels[] = { "aa", "dd", "ff", "jj", "ss", "zz" };

void
main()
  {
  const unsigned count = sizeof( labels ) / sizeof( labels[ 0 ] );
  if ( binary_search( labels, labels + count, "ff", str_compare ))
    cout << "ff is in labels.\n";
  else
    cout << "ff is not in labels.\n";
  }

ff is in labels

binary_search

Library

Declaration

Complexity

Example <ospace/osstd/examples/binsrch1.cpp>

Example <ospace/osstd/examples/binsrch2.cpp>