CODEWITHSUNDEEP
c++stl
David
David

Reputation: 4818

binary_search in c++ unexpected behaviour

The following snippet is returning me 0. I expected it to be 1. What's wrong going on here? 

#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 
}

I am using gcc /usr/lib/gcc/i686-linux-gnu/4.6/lto-wrapper

Upvotes: 1

Views: 321

Answers (4)

AnT stands with Russia
AnT stands with Russia

Reputation: 320361

"Unexpected behavior"? There's nothing unexpected here.

The whole idea of binary search algorithm is taking advantage of the fact that the input array is sorted. If the array is not sorted, there can't be any binary search on it.

When you use std::binary_search (as well as all other standard binary search-based algorithms), the input sequence must be sorted in accordance with the same comparison predicate as the one used by std::binary_search. Since you did not pass any custom predicate to std::binary_search, it will use the ordering defined by < operator. That means that your input Sequence of integers must be sorted in ascending order.

In your case the input sequence does not satisfy that requirement. std::binary_search cannot be used on it.

Upvotes: 4

RiaD
RiaD

Reputation: 47619

Your array is not sorted, so binary_search got undefined behavior. Try std::find instead

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

§25.4.3.4 of the C++11 standard (3242 draft)

  1. Requires: The elements e of [first,last) are partitioned with respect to the expressions e < value and !(value < e) or comp(e, value) and !comp(value, e). Also, for all elements e of [first, last), e < value implies !(value < e) or comp(e, value) implies !comp(value, e).

Upvotes: 4

Brian Cain
Brian Cain

Reputation: 14619

binary_search says:

Checks if the sorted range [first, last) contains an element equal to value. The first version uses operator< to compare the elements, the second version uses the given comparison function comp.

Your list is not sorted, it contains the elements 11 and 22 prior to 10.

Upvotes: 4

milleniumbug
milleniumbug

Reputation: 15804

I ran the program and saw this:

11
22
10
20
30
40
50

Binary Search -  0

Your array is not sorted, therefore, binary search fails. (it sees 11 in the first position, and concludes 10 does not exist here)

You either want to ensure the array is sorted before binary searching or use the regular std::find.

Upvotes: 13

Related Questions