binary_search

Синтаксис:

    #include <algorithm>
    bool binary_search( forward_iterator start, forward_iterator end, const T& val );
    bool binary_search( forward_iterator start, forward_iterator end, const T& val, Comp f );

Функция binary_search() просматривает элементы от start до end в поисках значения val. Просматриваемые элементы между start и end должны быть упорядочены по возрастанию, что определено оператором <. Обратите внимание, что бинарный поиск не будет работать, пока просматриваемые элементы не будут упорядочены.

Только оператор < должен быть определен для значений. Два значения a и b равны, если истинно выражение !(a<b) && !(b<a).

Если значение val найдено, binary_search() возвращает истину, иначе ложь. Если функция f определена, то она используется для сравнения элементов вместо оператора <.

binary_search() работает за логарифмическое время.

Например, следующий код использует binary_search(), чтобы определить, есть ли числа 0-9 в массиве целых чисел (nums[] должен быть упорядочен по возрастанию):

   int nums[] = { -242, -1, 0, 5, 8, 9, 11 };
   int start = 0;
   int end = 7;
 
   for( int i = 0; i < 10; i++ ) {
     if( binary_search( nums+start, nums+end, i ) ) {
       cout << "nums[] contains " << i << endl;
     } else {
       cout << "nums[] DOES NOT contain " << i << endl;
     }
   }

Этот код выводит:

   nums[] contains 0
   nums[] DOES NOT contain 1
   nums[] DOES NOT contain 2
   nums[] DOES NOT contain 3
   nums[] DOES NOT contain 4
   nums[] contains 5
   nums[] DOES NOT contain 6
   nums[] DOES NOT contain 7
   nums[] contains 8
   nums[] contains 9

Смотрите также: equal_range, lower_bound, partial_sort, partial_sort_copy, sort, stable_sort, upper_bound