为什么 binary_search() 和 find() 在这里的工作方式不同？

Question

如果我运行下面的代码，我得到的错误是 prog.cpp:7:39: error: no match对于 'operator=='（操作数类型是 'bool' 和 'std::vector::iterator {aka __gnu_cxx::__normal_iterator, std::vector >}'） if(binary_search(v.begin(),v.end(),3) == v.end()) cout<<"未找到";*

但是如果我使用 find() 而不是 binary_search() 我会得到预期的结果。这两个函数 return 只是一个迭代器，但为什么在这种情况下它们的行为不同？

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

Answer 1

std::find 和 std::binary_search 做不同的事情。

std::find returns 指向已找到元素的迭代器（如果未找到，则为 end()）。它不需要订购范围。
std::binary_searchreturns一个bool、true或false。它需要订购范围。

如果您想要结合二分搜索算法和来查找匹配的实际元素，您可以使用 std::lower_bound, std::upper_bound or std::equal_range。我将使用 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

为什么 binary_search() 和 find() 在这里的工作方式不同？

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

c++

stl

binary-search

stdvector