二进制搜索代码失败的效率检查

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

这对数组中的100万项进行了性能测试。我有点搞不懂为什么。是因为我从向量中创造了一个新的结构吗？是否涉及在内存中的新位置复制所有项目？

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