C++ binary_search()
C++算法binary_search()
C++算法 binary_search()函数用于检查[first，last)范围内的元素是否等效于val(或二进制谓词)，否则返回false。
范围[first，last)必须满足以下所有条件: 已针对元素 val或comp(element，val)进行了分区。 针对!(val < element)或!comp(value，element)进行了分区 对于所有元素，如果element val或comp(element，val)为true，则!(val < element)或!comp(val，element)也为true。
第一个版本使用operator 来比较元素，第二个版本使用给定的比较函数，即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。
复杂度
平均而言，复杂度在第一个和最后一个之间的距离是对数的: 最多执行log2(N)+ 2个元素比较，其中N =最后-第一个。
数据争用
访问[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;
}
输出:
示例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.
