C++ STL List的二分查找 |21xrx.com

C++ STL List的二分查找

2023-06-29 09:23:00 深夜i -- --

C++ STL List 二分查找

C++ STL List是一个非常常用的容器，常用于链表操作。当我们需要在List中进行二分查找时，其实是比较困难的。因为List不像vector那样，可以通过下标定位元素，所以我们不能再使用STL提供的二分查找函数了。

但是，值得注意的是List容器本身提供了sort函数，我们可以利用这个特性进行二分查找，具体步骤如下：

1.首先使用sort函数将List中的元素进行排序。

2.使用lower_bound和upper_bound函数进行查找。

下面是一段示例代码：


#include <iostream>
#include <list>
using namespace std;
int main()
{
  list<int> myList;
  myList.push_back(5);
  myList.push_back(3);
  myList.push_back(9);
  myList.push_back(6);
  myList.push_back(4);
  myList.sort(); // 先进行排序
  list<int>::iterator iter;
  iter = lower_bound(myList.begin(), myList.end(), 5); // 使用lower_bound查找大于等于5的第一个元素
  cout << "lower_bound查找结果：" << *iter << endl;
  iter = upper_bound(myList.begin(), myList.end(), 5); // 使用upper_bound查找大于5的第一个元素
  cout << "upper_bound查找结果：" << *iter << endl;
  return 0;
}

输出结果为：

lower_bound查找结果：5 upper_bound查找结果：6

可以看到，利用List容器自身的sort函数以及STL提供的lower_bound和upper_bound函数，我们可以轻松实现对List容器的二分查找。如果我们需要在自己的项目中使用二分查找，不妨尝试一下这种方法。

上一篇: idea打包java可执行jar包

下一篇: C++的三大特性

评论区

()

相似文章