C++ STL 二叉搜索

Harshit Jindal 2023年1月30日 2021年2月28日

C++ C++ Algorithm

C++ STL binary_search() 概述
二叉搜索的 C++ 程序

注意

如果你想详细了解二叉搜索，那么可以参考二叉搜索算法一文。

C++ 为我们提供了一个现成的函数 binary_search()，这样我们就不用自己去实现这个函数了。它是一种非常简单的使用和有效实现的方法，而且不容易出错。

C++ STL `binary_search()` 概述

语法

DEFAULT:       
template <class ForwardIterator, class T>  
bool binary_search (ForwardIterator first, ForwardIterator last, const T& val);  
  
CUSTOM COMPARISON FUNCTION:     
template <class ForwardIterator, class T, class Compare>  
bool binary_search (ForwardIterator first, ForwardIterator last, const T& val, Compare comp);

这里，T 可以是以下任何一种：int、float、short、long、byte、char、double，甚至用户定义的 Object。

它使用二叉搜索算法检查 [first, last) 内的元素是否与目标元素 X 匹配。默认情况下，它使用小于操作符来比较元素，但我们也可以提供我们自己的自定义 comp，如上面给出的第二个模板所述。

参数


`first`	指向给定数组范围内第一个元素的前向迭代器。
`last`	指向给定数组范围内最后一个元素的前向迭代器。
`comp`	一个用户定义的二进制谓词函数，接受两个正向迭代器作为参数，如果两个参数以正确的顺序出现，则返回 `true`。它不修改任何参数，并遵循严格的弱排序来排列元素。
`val`	我们在给定数组范围内搜索的目标元素。

返回值

如果找到目标元素，则返回 true，否则返回 false。

二叉搜索的 C++ 程序

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

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

    if (binary_search(v.begin(), v.end(), 5)) {
        cout << "Element found" << endl;
    }
    else {
        cout << "Element not found" << endl;
    }

    return 0;
}

Author: Harshit Jindal

Harshit Jindal has done his Bachelors in Computer Science Engineering(2021) from DTU. He has always been a problem solver and now turned that into his profession. Currently working at M365 Cloud Security team(Torus) on Cloud Security Services and Datacenter Buildout Automation.

C++ STL binary_search() 概述

语法

参数

返回值

二叉搜索的 C++ 程序

相关文章 - C++ Algorithm

C++ STL `binary_search()` 概述