C++ STL 中的二分查找函数
c++server side programmingprogramming
二分查找是一种在排序数组中找到目标值位置的搜索算法。二分查找将目标值与排序数组的中间元素进行比较。二分查找的时间复杂度为 O(1)。这是一个 C++ 程序，我们在其中实现了各种。C++ STL 中的二分查找函数
算法
开始 初始化整数值向量。 这里使用的函数: binary_search(start_pointer, end_pointer, value) = 如果值存在于数组中，则返回 true，否则返回 false。 lower_bound(start_pointer, end_pointer, value) = 如果容器 包含 1 个值，则返回指向"值的位置"的指针。如果容器 包含多个值，则返回指向"值的第一个位置"的指针。如果容器 不包含值的出现，则返回指向"下一个比值更大的数字的位置"的指针。 upper_bound(start_pointer, end_pointer, value) = 如果容器 包含 1 个值，则返回指向"下一个比值更大的值的位置"的指针。返回指向"下一个比值最后一次出现的更高的数字的第一个位置"的指针如果容器包含多个值。如果容器不包含值的出现，则返回 指向"下一个比值更大的数字的位置"的指针。 打印结果。 结束。
示例代码
#include<bits/stdc++.h>
using namespace std;
int main() {
vector<int> a = {6,7,10,14,16,20};
if (binary_search(a.begin(), a.end(), 50))
cout << "50 exists in vector";
else
cout << "50 does not exist";
cout << endl;
if (binary_search(a.begin(), a.end(), 7))
cout << "7 exists in the vector";
else
cout << "7 does not exist";
cout << endl;
cout << "The position of 7 using lower_bound ";
cout << lower_bound(a.begin(), a.end(), 7) - a.begin();
cout << endl;
cout << "The position of 7 using upper_bound ";
cout << upper_bound(a.begin(), a.end(), 7) - a.begin();
cout << endl;
}
输出
50 does not exist 7 exists in the vector The position of 7 using lower_bound 1 The position of 7 using upper_bound 2
