Why does binary_search() and find() work differently here?

Question

If I run the following code, I get the error as prog.cpp:7:39: error: no match for ‘operator==’ (operand types are ‘bool’ and ‘std::vector::iterator {aka __gnu_cxx::__normal_iterator<int, std::vector >}’) if(binary_search(v.begin(),v.end(),3) == v.end()) cout<<"not found";*

But if I use find() instead of binary_search() I get the result as expected. Both these functions return an iterator only, But why are they acting differently in this situation?

#include <bits/stdc++.h>
using namespace std;

int main ()
{
  vector < int >v = { 1, 2, 3, 5 };
  
  if (binary_search (v.begin (), v.end (), 3) == v.end ())
    cout << "not found";
  else
    cout << "found";
}

Please check what [`std::binary_search`](https://en.cppreference.com/w/cpp/algorithm/binary_search) really returns. — Some programmer dude, Oct 01 '20 at 07:48
Unrelated: [Why should I not `#include `?](https://stackoverflow.com/Questions/31816095/Why-Should-I-Not-Include-Bits-Stdc-H.) and [Why is `using namespace std;` considered bad practice?](https://stackoverflow.com/questions/1452721/why-is-using-namespace-std-considered-bad-practice) — Ted Lyngmo, Oct 01 '20 at 07:56

Ted Lyngmo · Accepted Answer · 2020-10-01T08:23:57.553

std::find and std::binary_search do different things.

std::find returns an iterator to the found element (or end() if it's not found). It does not require the range to be ordered.
std::binary_search returns a bool, true or false. It requires the range to be ordered.

If you'd like a combination of both a binary search algorithm and finding the actual element(s) that matches, you can use std::lower_bound, std::upper_bound or std::equal_range. I'll give an example using std::equal_range:

#include <algorithm>
#include <iostream>
#include <vector>

int main () {
    std::vector v = { 1, 2, 3, 3, 5 };

    std::cout << std::boolalpha
        << std::binary_search (v.begin(), v.end(), 3) << '\n' // prints true
        << std::binary_search (v.begin(), v.end(), 4) << '\n' // prints false
    ;

    auto[first, last] = std::equal_range(v.begin(), v.end(), 3);
    
    if(first != last) std::cout << "found\n";    // prints found
    else std::cout << "not found\n";
    
    for(;first != last; ++first) std::cout << *first << '\n'; // prints 3 twice
}

Demo

Why does binary_search() and find() work differently here?

1 Answers1