二进制搜索代码无法进行效率检查

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)空间,所以更糟糕).您应该在调用中直接使用数组,binary_search就像使用以下内容创建向量一样:

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