21xrx.com
2024-11-22 08:17:26 Friday
登录
文章检索 我的文章 写文章
C++ Vector的查找方法
2023-07-12 06:00:58 深夜i     --     --
C++ Vector 查找方法

C++是一种广泛使用的编程语言,其中的Vector是一个非常有用的容器,能够动态调整其大小并提供高效的操作。在程序中,经常需要查找Vector中的特定元素,本文将介绍C++ Vector的查找方法。

一、线性查找

线性查找是最简单的一种查找方法。它从Vector的第一个元素开始依次查找,直到找到目标元素或遍历完整个Vector。代码实现如下:

vector v 4;

int target = 3;

for(int i = 0; i < v.size(); i++){

  if(v[i] == target)

    cout << "Found at index " << i << endl;

    break;

}

二、二分查找

在有序的Vector中,二分查找是一种高效的查找方法。它将目标元素与Vector中间的元素比较,然后根据结果缩小搜索范围。如果目标元素等于中间元素,则查找结束。否则,根据中间元素与目标元素的大小关系调整搜索范围并继续查找,直到找到目标元素或无法再缩小搜索范围。代码实现如下:

vector v 4;

int target = 3;

int left = 0;

int right = v.size() - 1;

while(left <= right){

  int mid = left + (right - left) / 2;

  if(v[mid] == target)

    cout << "Found at index " << mid << endl;

    break;

  else if(v[mid] < target){

    left = mid + 1;

  }

  else

    right = mid - 1;

}

三、STL库中的查找函数

C++ STL库提供了多种查找函数来帮助我们查找Vector中的特定元素,例如find()、binary_search()、lower_bound()、upper_bound()等函数。这些函数可以根据不同的需求选择最适合的一个。比方说,如果我们只需要找到第一次出现目标元素的位置,可以使用find()函数;如果目标元素大于Vector中的任何元素,可以使用upper_bound()函数。代码示例如下:

vector v 3;

int target = 3;

auto it = find(v.begin(), v.end(), target);

if(it != v.end()){

  cout << "Found at index " << distance(v.begin(), it) << endl;

}

vector v 2;

int target = 6;

if(binary_search(v.begin(), v.end(), target))

  cout << "Found" << endl;

else

  cout << "Not Found" << endl;

vector v 5;

int target = 3;

auto it = lower_bound(v.begin(), v.end(), target);

cout << "Lower bound at " << distance(v.begin(), it) << endl;

vector v 3;

int target = 6;

auto it = upper_bound(v.begin(), v.end(), target);

cout << "Upper bound at " << distance(v.begin(), it) << endl;

综上所述,C++ Vector的查找方法包括线性查找、二分查找和STL库中的查找函数。编写程序时应根据不同情况选择最适合的查找方法,提高程序的效率。

  
  
下一篇: 考试题目整理

评论区

{{item['qq_nickname']}}
()
回复
回复