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

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;
}

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

Answer 1

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

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

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

Binary search code fails efficiency check

c++

performance

search

binary-search