c++ - 二进制搜索代码未通过效率检查

Question

我的任务是完成一项涉及简单 C++ 编码练习的职位的技术评估。问题是检查排序数组中是否存在数字，其中:

• ints[] 是要排序的数组
• size是数组的大小
• k是要检查的数

要求是实现一个使用尽可能少的 CPU 周期的解决方案。我的解决方案如下:

static bool exists(int ints[], int size, int k)
{
    std::vector<int> v(ints,ints+size);

    if (std::binary_search (v.begin(), v.end(), k))
        return true;

    return false;
}

这未能通过数组中一百万项的性能测试。我对为什么有点困惑。是不是我正在从 vector 创建一个新结构？它是否涉及将所有项目复制到内存中的新位置？

Answer 1

std::vector<int> v(ints,ints+size);将复制您的数组。您真的不想在二进制搜索函数中执行此操作，因为它是 O(N) 操作。这完全支配了二进制搜索的 O(logN) 并使您的算法等同于线性搜索(更糟的是因为您还消耗了 O(N) 空间)。您应该在对 binary_search 的调用中直接使用数组就像您使用以下方法创建 vector 一样:

static bool exists(int ints[], int size, int k)
{
    return std::binary_search(ints, ints+size, k);
}