set二分查找代码展示
时间: 2023-10-14 17:06:33 浏览: 34
以下是一个简单的 set 二分查找的代码展示:
```
#include <iostream>
#include <set>
using namespace std;
int main() {
set<int> s{1, 3, 5, 7, 9};
int x = 4;
auto it = s.lower_bound(x);
if (it == s.begin()) {
cout << "Not Found\n";
} else {
it--;
cout << *it << "\n";
}
return 0;
}
```
该代码会先构建一个 set 容器,并在其中插入一些数据。然后,它会尝试查找 x 是否在该 set 中存在。如果存在,那么它会返回该元素的迭代器;如果不存在,那么它会返回指向第一个大于等于 x 的元素的迭代器。最后,我们通过 `lower_bound` 函数得到的迭代器来判断是否需要输出 "Not Found"。
相关问题
c++ set二分查找
在C++中,std::set是一个实现了红黑树的有序容器。虽然std::set本身没有提供二分查找的函数,但是可以通过std::set的成员函数lower_bound来实现二分查找。
下面是一个示例代码,演示了如何使用std::set进行二分查找:
```cpp
#include <iostream>
#include <set>
int main() {
std::set<int> mySet = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
int target = 6;
auto it = mySet.lower_bound(target); // lower_bound返回第一个不小于target的迭代器
if (it != mySet.end() && *it == target) {
std::cout << "找到了目标元素 " << target << std::endl;
} else {
std::cout << "未找到目标元素 " << target << std::endl;
}
return 0;
}
```
在这个示例中,我们创建了一个std::set,并在其中插入了一些整数。然后,我们设定了目标元素为6,并使用lower_bound函数来查找第一个不小于目标元素的迭代器。
如果找到了目标元素,那么lower_bound返回的迭代器指向这个元素,并且我们可以通过解引用操作获得该元素的值。如果没有找到目标元素,lower_bound返回的迭代器将指向大于目标元素的最小元素,或者是std::set的end迭代器。
请注意,std::set的lower_bound函数的时间复杂度为O(logN),其中N是std::set中元素的数量。
set结构体二分查找
在C++的STL库中,set是一种有序的容器,它使用红黑树实现。由于set是有序的,所以可以使用二分查找算法在set结构体中查找元素。
在C++中,使用STL库的set结构体进行二分查找可以通过调用set的成员函数lower_bound()实现。lower_bound()函数返回一个迭代器,该迭代器指向第一个不小于指定值的元素。如果找不到这样的元素,lower_bound()函数将返回迭代器指向set的end()位置。
以下是使用set结构体进行二分查找的代码示例:
```
#include <iostream>
#include <set>
int main() {
std::set<int> mySet = {1, 2, 3, 4, 5, 6, 7, 8};
int target1 = 0;
auto it1 = mySet.lower_bound(target1);
if (it1 != mySet.end() && *it1 == target1) {
std::cout << "Element " << target1 << " found at position " << std::distance(mySet.begin(), it1) << std::endl;
} else {
std::cout << "Element " << target1 << " not found in the set." << std::endl;
}
int target2 = 6;
auto it2 = mySet.lower_bound(target2);
if (it2 != mySet.end() && *it2 == target2) {
std::cout << "Element " << target2 << " found at position " << std::distance(mySet.begin(), it2) << std::endl;
} else {
std::cout << "Element " << target2 << " not found in the set." << std::endl;
}
int target3 = 111;
auto it3 = mySet.lower_bound(target3);
if (it3 != mySet.end() && *it3 == target3) {
std::cout << "Element " << target3 << " found at position " << std::distance(mySet.begin(), it3) << std::endl;
} else {
std::cout << "Element " << target3 << " not found in the set." << std::endl;
}
return 0;
}
```
请注意,为了使用set结构体进行二分查找,你需要在程序中包含头文件<set>。
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)