binary_search в C++ неожиданном поведении

Question

Следующий фрагмент возвращает мне 0. Я ожидал, что это будет 1. Что здесь происходит?

#include <iostream> 
#include <iterator> 
#include <ostream> 
#include <algorithm> 
#include <vector> 
using namespace std; 
int main(){ 
    vector<int> v; 
    int arr[] = {10,20,30,40,50}; 
    v.push_back(11); 
    v.push_back(22); 
    copy(arr,arr + sizeof(arr)/sizeof(arr[0]),back_inserter(v)); // back_inserter makes space starting from the end of vector v 
    for(auto i = v.begin(); i != v.end(); ++i){ 
    cout << *i << endl; 
    } 
    cout << endl << "Binary Search - " << binary_search(v.begin(), v.end(), 10) <<endl; // returns bool 
} 

Я использую GCC /usr/lib/gcc/i686-linux-gnu/4.6/lto-wrapper

Answer 1

Я запустил программу и увидел это:

11 
22 
10 
20 
30 
40 
50 

Binary Search - 0 

Ваш массив не сортируется, поэтому двоичный поиск не выполняется. (Он видит 11 в первом положении, и делается вывод о 10 здесь не существует)

Вы либо хотите, чтобы убедиться, что массив отсортирован перед тем бинарного поиска или использовать обычный std::find.

Answer 2

binary_search говорит:

Проверяет отсортированный диапазон [first, last) содержит элемент, равный value. В первой версии для сравнения элементов используется operator<, вторая версия использует данную функцию сравнения comp.

Ваш список не отсортирован, она содержит элементы 11 и 22 До 10.

Answer 3

Ваш массив не отсортирован, поэтому binary_search получил неопределенное поведение. Попытка std::find вместо

bool found = std::find(v.begin(), v.end(), 10) != v.end() 

§ 25.4.3.4 стандартного (3242) проекта C++ 11

1. Требует: Элементы е [первый, последний) разделены по отношению к выражения e < value и! (значение < e) или comp (e, значение) и! comp (значение, e). Кроме того, для всех элементов e из [first, last] значение e< означает значение (значение < e) или comp (e, value). Comp (value, e).

Answer 4

"Неожиданное поведение"? Здесь нет ничего неожиданного.

Вся идея алгоритма бинарного поиска использует тот факт, что входной массив равен , отсортированный. Если массив не отсортирован, на нем не может быть бинарного поиска.

При использовании std::binary_search (а также всех других стандартных алгоритмов на основе бинарного поиска) последовательность ввода должна сортироваться в соответствии с одним и тем же предикатом сравнения, который используется для std::binary_search. Поскольку вы не передали какой-либо пользовательский предикат до std::binary_search, он будет использовать порядок, определенный оператором <. Это означает, что ваш ввод последовательности целых чисел должен быть отсортирован в порядке возрастания.

В вашем случае входная последовательность не удовлетворяет этому требованию. std::binary_search не может быть использован на нем.