C++ 算法 binary_search()

2024年8月30日 | 阅读4分钟

C++ 算法 binary_search() 函数用于检查范围 [first, last) 中的元素是否与 val（或二元谓词）等效，否则返回 false。

范围 [first, last) 必须满足以下所有条件：
- 相对于 element < val 或 comp (element, val) 进行分区。
- 相对于 !(val < element) 或 !comp(value, element) 进行分区。
- 对于所有元素，如果 element < val 或 comp (element, val) 为 true，则 !(val < element) 或 !comp(val, element) 也为 true。
第一个版本使用运算符 < 比较元素，第二个版本使用给定的比较函数，即 comp。

语法

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);

参数

first: 指向要搜索的范围中第一个元素的前向迭代器。

last: 指向要搜索的范围中最后一个元素之后的前向迭代器。

comp：一个用户定义的二元谓词函数，接受两个参数，如果这两个参数有序则返回true，否则返回false。它遵循严格的弱排序来对元素进行排序。

val: 用于比较范围内元素的上界值。

返回值

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

复杂度

平均而言，复杂度与 first 和 last 之间的距离成对数关系：执行最多 log2 (N) + 2 次元素比较，其中 N = last - first。

数据竞争

访问范围 [first, last) 中的对象。

异常

如果元素比较或迭代器操作抛出异常，此函数将抛出异常。

请注意，无效参数会导致未定义行为。

示例 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

示例 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.

示例 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.

示例 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.

下一主题C++ 算法

C++ 算法 binary_search()

语法

参数

返回值

复杂度

数据竞争

异常

示例 1

示例 2

示例 3

示例 4

联系信息

关注我们

教程

面试题

在线编译器

Python

Java

.Net Framework

AI, ML and Data Science

Cloud Technology

B.Tech and MCA

Web Technology

PHP

Software Testing

Technical Interview

Java Interview

Python

Web Interview

Database Interview

B.Tech / MCA

Important Interview

Software Testing Interview

Company Interviews

Online Compilers

Multiple Choice Questions

C++ 教程

C++ 控制语句

C++ 函数

C++ 数组

C++ 类和对象

C++ 构造函数

C++ 继承

C++ 多态

C++ 抽象

C++ 命名空间

C++ 模板

C++ 字符串

C++ 指针

信号处理

C++ 异常

C++ 文件与流

C++ STL 教程

面试题

选择题

C++ 程序

C++ STL Stack

C++ STL Bitset

C++ STL Deque

C++ STL List

C++ STL Map

C++ STL Math

C++ STL priority_queue

C++ STL Queue

C++ STL Multiset

C++ STL Multimap

C++ STL Set

C++ STD Strings

C++ STL Vector

C++ 操纵符

C++ STL Algorithms

C++ Algorithm

C++ Iterators

C++ 杂项

C++ 算法 binary_search()

语法

参数

返回值

复杂度

数据竞争

异常

示例 1

示例 2

示例 3

示例 4

相关帖子

algorithm shuffle() 函数

algorithm is_partitioned() 函数

algorithm equal() 函数

algorithm stable_partition() 函数

algorithm set_union() 函数

algorithm any_of() 函数

algorithm mismatch() 函数

algorithm partition() 函数

algorithm move() 函数

algorithm count() 函数