Previous fileTop of DocumentContentsIndex pageNext file
Apache C++ Standard Library Reference Guide

binary_search()

Library:  Algorithms


Function

Local Index

No Entries

Summary

Algorithm that performs a binary search for a value

Synopsis

#include <algorithm>

namespace std {
  template <class ForwardIterator, class T>
  bool
  binary_search(ForwardIterator start, ForwardIterator finish,
                const T& value);
  template <class ForwardIterator, class T, class Compare>
  bool
  binary_search(ForwardIterator start, ForwardIterator finish,
                const T& value, Compare comp);
}

Description

The binary_search() algorithm, like the related algorithms equal_range(), lower_bound(), and upper_bound(), performs a binary search on a range of ordered values. All binary search algorithms have two variations. The first variation uses the operator< to perform the comparison, and assumes that the sequence has been sorted using that operator. The second variation allows you to specify 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 variation of binary_search() returns true if the sequence contains at least one element that is equal to the search value. The second variation 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 [start, finish) that satisfies the corresponding conditions:

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

or

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

Complexity

binary_search() performs at most log(finish - start) + 2 comparisons.

Example

See Also

equal_range(), lower_bound(), upper_bound()

Standards Conformance

ISO/IEC 14882:1998 -- International Standard for Information Systems -- Programming Language C++, Section 25.3.3.4



Previous fileTop of DocumentContentsIndex pageNext file