Skip to content. Skip to navigation

ICTP Portal

You are here: Home Manuals on-line PGI Compiler pgC_lib binary_search
Personal tools
Document Actions


Click on the banner to return to the class reference home page.




Performs a binary search for a value on a container.

Data Type and Member Function Indexes
(exclusive of constructors and destructors)



#include <algorithm>

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

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


The binary_search algorithm, like other related algorithms (equal_range, lower_bound and upper_bound) performs a binary search on ordered containers. All binary search algorithms have two versions. The first version uses the less than operator (operator<) to perform the comparison, and assumes that the sequence has been sorted using that operator. The second version allows you to include a function object of type Compare, which it assumes was the function used to sort the sequence. The function object must be a binary predicate.

The binary_search algorithm returns true if a sequence contains an element equivalent to the argument value. The first version of binary_search returns true if the sequence contains at least one element that is equal to the search value. The second version of the binary_search algorithm returns true if the sequence contains at least one element that satisfies the conditions of the comparison function. Formally, binary_search returns true if there is an iterator i in the range [first, last) that satisfies the corresponding conditions:

!(*i < value) && !(value < *i) 


comp(*i, value) == false && comp(value, *i) == false


binary_search performs at most log(last - first) + 2 comparisons.


   // b_search.cpp
 #include <vector>
 #include <algorithm>
 #include <iostream.h>

 int main()
   typedef vector<int>::iterator iterator;
   int d1[10] = {0,1,2,2,3,4,2,2,6,7};
   // Set up a vector
   vector<int> v1(d1,d1 + 10);
   // Try binary_search variants
   bool b1 = binary_search(v1.begin(),v1.end(),3);
   bool b2 =
   // Output results
   cout << "In the vector: ";
           ostream_iterator<int,char>(cout," "));

   cout << endl << "The number 3 was " 
        << (b1 ? "FOUND" : "NOT FOUND");
   cout << endl << "The number 11 was "
        << (b2 ? "FOUND" : "NOT FOUND") << endl;
   return 0;

Output : 
In the vector: 0 1 2 2 2 2 3 4 6 7
The number 3 was FOUND
The number 11 was NOT FOUND


If your compiler does not support default template parameters, then you need to always supply the Allocator template argument. For instance, you'll have to write:

vector<int,allocator<int> >

instead of:


See Also

equal_range, lower_bound, upper_bound

©Copyright 1996, Rogue Wave Software, Inc.

Powered by Plone This site conforms to the following standards: