C++ - 从两侧搜索数组

Question

在执行速度方面，第一个循环和第二个循环之间的速度有什么区别吗？我也在谈论比这个样本更大的阵列。

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

Answer 1

就 Big-O 时间而言，不，因为这两种方法都是 O(n)。
在第一个循环中，您迭代的次数更少，但每次迭代的计算量更多。在第二个循环中，每次迭代执行较少的计算，但总体上执行更多的迭代。我不希望两者之间有任何巨大的性能差异，如果您单步执行汇编代码，编译器甚至可能将两者更改为相同。
它还取决于您的 CPU 使用的缓存方案，因为在足够大的数组中，第一个循环可能会缓存两个内存块，而不是第二个只会缓存一个内存块。这可能会对 direct-mapped cache 产生不利影响。 ，因为 high 和 low 索引可能指的是占用同一个缓存 block 的内存位置，所以一个接一个地访问会导致不断的缓存未命中。
在这一点上，这真的取决于你想要完成什么更清楚，所以我推荐循环#2。更不用说，第二种方法更不容易出错。