关注我们

C++ 算法中的 binary_search函数

使用C++算法 binary_search()函数检查[first，last)参数内的元素是否等效于val(或二进制谓词)，否则返回false。

binary_search - 语法

default (1)       template <class ForwardIterator, class T>
                        bool binary_search (ForwardIterator first, ForwardIterator last,
                             const T& val);

custom (2)      template <class ForwardIterator, class T, class Compare>
                       bool binary_search (ForwardIterator first, ForwardIterator last,
                             const T& val, Compare comp);

binary_search - 参数

first:一个正向迭代器，指向要搜索参数内的第一个元素。

last:前向迭代器，指向要搜索参数内的最后一个最后一个元素。

comp :用户定义的二进制谓词函数，该函数接受两个参数，如果两个参数顺序正确，则返回true，否则返回false。

val :比较参数内元素的上限值。

binary_search - 返回值

如果找到等于val的元素，则返回true，否则返回false。

binary_search - 例子1

让我们看一个简单的例子来演示binary_search()的用法:

在线运行复制代码

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

using namespace std;

int main()
{
  vector<int> v = {3, 1, 4, 6, 5};

  if (binary_search(v.begin(), v.end(), 4)) {
    cout << "4 found" << endl;
  }
  else {
    cout << "4 not found" << endl;
  }
  
  return 0;
}

输出:

4 found

binary_search - 例子2

让我们看另一个简单的例子:

复制代码

#include <iostream>    //std::cout
#include <algorithm>   //std::binary_search, std::sort
#include <vector>      //std::vector

using namespace std;

bool myfunction (int i,int j) { return (i<j); }

int main () {
  int myints[] = {1,2,3,4,5,4,3,2,1};
  vector<int> v(myints,myints+9);                        //1 2 3 4 5 4 3 2 1

 //using default comparison:
  sort (v.begin(), v.end());

  cout << "looking for a 3... ";
  if (binary_search (v.begin(), v.end(), 3))
    cout << "found!\n"; else cout << "not found.\n";

 //using myfunction as comp:
  sort (v.begin(), v.end(), myfunction);

  cout << "looking for a 6... ";
  if (binary_search (v.begin(), v.end(), 6, myfunction))
    cout << "found!\n"; else std::cout << "not found.\n";

  return 0;
}

输出:

looking for a 3... found!
looking for a 6... not found.

binary_search - 例子3

让我们看另一个使用比较函数比较元素的简单示例:

在线运行复制代码

#include <iostream>
#include <vector>
#include <algorithm>
 
using namespace std;
 
int main()
{
  int a[] = {1, 2, 3, 4, 5, 6, 7, 9, 10};
  vector<int> v(a, a+9);
  cout <<"\nHere are the values in the vector:\n";
  for (vector<int>::size_type i=0; i<v.size(); i++)
    cout <<v.at(i)<<" ";
 
  if (binary_search(v.begin(), v.end(), 3))
    cout <<"\nThe value 3 was found.";
  else
    cout <<"\nThe value 3 was not found.";
 
  if (binary_search(v.begin(), v.end(), 8))
    cout <<"\nThe value 8 was found.";
  else
    cout <<"\nThe value 8 was not found.";
 
  return 0;
}

输出:

Here are the values in the vector:
1 2 3 4 5 6 7 9 10 
The value 3 was found.
The value 8 was not found.

binary_search - 例子4

让我们看另一个简单的例子:

复制代码

#include <iostream>
#include <algorithm>
#include <vector>
#include <functional>  
#include <iomanip>     
using namespace std;
 
void print(vector <int> vs)
{   
    vector <int>::iterator i;
    for(i = vs.begin(); i != vs.end(); i++)
    {
        cout << left << setw(2) << *i;
    }
    cout << endl;
}
 
int main () {
    int arr[] = {1, 5, 2, 9, 8, 4, 3, 7, 6};
    int alen = sizeof(arr)/sizeof(int);
    vector <int> v(arr, arr + alen); 
 
    sort (v.begin(), v.end());
    cout << "Sorted vector elements : ";
    print(v);
   //Searching without using predicate
    cout << "Searching for 4 : ";
    if (binary_search (v.begin(), v.end(), 4))
        cout << "found!" << endl;
    else
        cout << "not found." << endl;
   //Searching using predicate
    cout << "Searching for element greater than 9 : ";
    if (binary_search(v.begin(), v.end(), 9, greater<int>()))
        cout << "found!" << endl;
    else
        cout << "not found." << endl;
    return 0;
}

输出:

Sorted vector elements : 1 2 3 4 5 6 7 8 9 
Searching for 4 : found!
Searching for element greater than 9 : not found.

祝学习愉快！(内容编辑有误？请选中要编辑内容 -> 右键 -> 修改 -> 提交！)

技术教程推荐

React Hooks 核心原理与实战 -〔王沛〕

程序员的个人财富课 -〔王喆〕

云原生架构与GitOps实战 -〔王炜〕

好记忆不如烂笔头。留下您的足迹吧 :)

C++ 算法 中的 binary_search函数