C++ STL中的二分查找技巧 |21xrx.com

C++ STL中的二分查找技巧

2023-06-27 18:44:06 深夜i -- --

C++ STL 二分查找技巧

C++ STL（Standard Template Library）是C++编程语言中的一部分，提供了丰富的类模板和函数模板，可以大大简化开发者的工作，其中的二分查找技巧更是C++ STL中的重要部分。

二分查找是一种效率很高的查找算法，也叫折半查找。它的基本思想是在一个有序的列表中，每次查找都将待查找的值与列表中间位置的值进行比较，如果待查找的值比中间位置的值小，则接着在前一半继续查找；如果待查找的值比中间位置的值大，则接着在后一半继续查找，以此类推，最终找到待查找的值或确定其不存在。

C++ STL中的二分查找技巧可以使用STL提供的lower_bound()函数和upper_bound()函数来实现，它们都需要一个已经有序的集合和一个要查找的值作为参数，返回的是指向该值的迭代器。lower_bound()函数返回第一个不小于该值的元素的迭代器，而upper_bound()函数返回第一个大于该值的元素的迭代器。

下面是一个简单的示例，展示了如何使用C++ STL中的二分查找技巧：


#include <iostream>
#include <vector>
#include <algorithm>
int main() {
  std::vector<int> v 4;
  int n = 5;
  auto it = std::lower_bound(v.begin(), v.end(), n);
  if (it != v.end() && *it == n) {
    std::cout << "Value found at index: " << it - v.begin() << std::endl;
  }
  else
    std::cout << "Value not found!" << std::endl;
  
  return 0;
}

在上述示例中，我们创建了一个有序的vector，然后使用lower_bound()函数来查找值为5的元素。如果该值存在，就输出它的下标，否则输出找不到该值的提示。

通过使用C++ STL中的二分查找技巧，我们可以方便地在有序的集合中查找特定的元素。值得注意的是，我们需要先将集合进行排序，才能使用lower_bound()函数和upper_bound()函数。此外，lower_bound()函数和upper_bound()函数都有多种重载形式，详见C++标准库的文档。

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

下一篇: 如何使用C++开发安卓软件

评论区

()

相似文章