数据结构
网络
关系型数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济学
心理学
社会学
时尚研究
法律研究C++ STL 中的二分搜索函数
二分搜索是一种搜索算法，用于查找目标值在已排序数组中的位置。二分搜索将目标值与已排序数组的中间元素进行比较。二分搜索的时间复杂度为 O(1)。这是一个 C++ 程序，其中我们实现了各种。C++ STL 中二分搜索函数
算法
Begin Initialize the vector of integer values. The functions are used here: binary_search(start_pointer, end_pointer, value) = Returns true if the value present in array otherwise false. lower_bound(start_pointer, end_pointer, value) = Returns pointer to “position of value” if container contains 1 occurrence of value. Returns pointer to “first position of value” if container contains multiple occurrence of value. Returns pointer to “position of next higher number than value” if container does not contain occurrence of value. upper_bound(start_pointer, end_pointer, value) = Returns pointer to “position of next higher valuethan value” if container contains 1 occurrence of value. Returns pointer to “first position of next higher number than last occurrence of value” if container contains multiple occurrence of value. Returns pointer to “position of next higher number than value” if container does not contain occurrence of value. Print the results. End.
示例代码
#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
更新于: 30-7-2019
918 浏览量
广告