C++ STL 二叉搜尋
Harshit Jindal
2023年1月30日
2021年2月28日
注意
如果你想詳細瞭解二叉搜尋,那麼可以參考二叉搜尋演算法一文。
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.
LinkedIn