c++ - C++-从两侧搜索数组

在执行速度上，第一个循环和第二个循环之间的速度是否有差异？我还说的是比这个样本更大的数组。

int main()
{
    int n = 17;
    int posz = 7;
    int array[] = {0, 1, 9, 2, 8, 3, 8, 5, 4, 7, 6, 10, 23, 43, 123, 54, 76, 34};
    for (int i = 0; i < (n / 2) + 1; i++)
    {
        if (array[i] == posz || array[n - 1 - i] == posz)
        {
            std::cout << "found\n";
            break;
        }
    }

    for (int i = 0; i < n; i++)
    {
        if (array[i] == posz)
        {
            std::cout << "found\n";
            break;
        }
    }

    return 0;
}

最佳答案

就Big-O时间而言，否，因为这两种方法均为O(n)。
在第一个循环中，您迭代的次数更少，但是每次迭代都要进行更多的计算。在第二个循环中，您每次迭代执行的计算较少，但总体上进行了更多的迭代。我不希望两者之间有巨大的性能差异，并且如果您逐步执行汇编代码，编译器甚至可能会将两者更改为相同。
这还取决于您的CPU使用的缓存方案，因为在足够大的阵列中，第一个循环可以缓存两个内存块，而不是第二个循环仅缓存一个内存块。这可能会对direct-mapped cache产生不利影响，因为高索引和低索引可能引用占用相同缓存块的内存位置，因此，一个接一个地访问将导致持续的缓存未命中。
在这一点上，这实际上取决于您要完成的工作，因此我建议循环2。更不用说，第二种方法更不容易出错。

关于c++ - C++-从两侧搜索数组，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/64637340/