在向量中寻找项目

Question

我有一个实数值向量，按升序排序。

这些值可以在 [0, 1] 范围内。然后我在这个范围内选择一个值 x 并且我需要找到哪个是大于或等于 x.

的较小值的索引

我可以通过遍历整个数组来解决这个问题：

vector<double> values;
double x;

for (auto val : values)
{
    if (x <= values)
    {
        // found
        break;
    }
}

有没有更快的方法来获得相同的结果？我在想二分查找，但是怎么实现呢？

Answer 1

你知道 SO 不是一个你要求别人给你写代码的网站，所以以 std::binary_search 这个例子来做你的方式：

// binary_search example
#include <iostream>     // std::cout
#include <algorithm>    // std::binary_search, std::sort
#include <vector>       // std::vector

bool myfunction (int i,int j) { return (i<j); }

int main () {
  int myints[] = {1,2,3,4,5,4,3,2,1};
  std::vector<int> v(myints,myints+9);                         // 1 2 3 4 5 4 3 2 1

  // using default comparison:
  std::sort (v.begin(), v.end());

  std::cout << "looking for a 3... ";
  if (std::binary_search (v.begin(), v.end(), 3))
    std::cout << "found!\n"; else std::cout << "not found.\n";

  // using myfunction as comp:
  std::sort (v.begin(), v.end(), myfunction);

  std::cout << "looking for a 6... ";
  if (std::binary_search (v.begin(), v.end(), 6, myfunction))
    std::cout << "found!\n"; else std::cout << "not found.\n";

  return 0;
}

正如 Piotr 所说，这不会给您索引，而是 yes/no 答案。但是，这应该是最简单的方法，因此也是最快的。

Answer 2

您可以使用 operator[] 像数组一样直接访问向量中的项目，而不是使用迭代器从头开始。我假设您已经知道二进制搜索。用数组实现，随处可见，这里就不多说了。只需将向量视为数组即可。

Answer 3

使用std::lower_bound:

#include <iterator>
#include <algorithm>

std::distance(begin(values)
            , std::lower_bound(begin(values), end(values), x));

如果该项目不存在，它会给你一个比最后一个元素大 1 的索引。

DEMO

Answer 4

函数lower_bound可能会满足您的需求，您可以像下面这样使用它：

iter =lower_bound(values.begin(),values.end(),x);

在向量中寻找项目

Seek item within vector

c++

sorting

search

binary-search

c++11