时间戳

首页 > 解决方案 > 为什么 binary_search() 和 find() 在这里的工作方式不同？

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

问题描述

如果我运行以下代码，我会得到错误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<<"未找到"; *

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

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

标签： c++stlbinary-searchstdvector

解决方案

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

  • std::find返回一个指向找到的元素的迭代器（或者end()如果它没有找到）。它不需要订购范围。
  • std::binary_search返回一个bool,true或false. 它需要订购的范围。

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

演示

推荐阅读