这是加快数组处理速度的好方法吗?

Question

所以，今天我醒悟了这个想法。

只要假设你有一个很长的东西列表，一个数组，你必须检查每一个，找到与你要找的东西匹配的那个。为此，您可以使用for循环。现在，想象一下您要查找的那个几乎位于列表的末尾，但您不知道。因此，在这种情况下，假设检查列表元素的顺序无关紧要，那么从最后一个元素而不是第一个元素开始会更方便，只是为了节省一些时间和内存。但是，如果您的元素几乎处于开头怎么办？

那时我想：如果我能同时开始检查列表两端的元素会怎样？

因此，经过几次尝试，我想出了这个原始示例代码(用js编写的(，在我看来，它将解决我们上面定义的问题：

fx (var list) {
    var len = length(list);
    // To save some time as we were saying, we could check first if the array isn't as long as we were expecting
    if (len == 0) {
        // If it's not, then we just process the only element anyway
        /*
        ...
        list[0]
        ...
        */
        return;
    } else {
        // So, now here's the thing. The number of loops won't be the length of the list but just half of it.
        for (var i = 0; i == len/2; i++) {
            // And inside each loop we process both the first and last elements and so on until we reach the middle or find the one we're looking, whatever happens first
            /*
            ...
            list[i]
            list[len]
            ...
            */
            len--;
        }
    }
    return;
};

无论如何，我仍然不完全确定这是否真的会加快过程或使其变慢或根本没有任何区别。这就是为什么我需要你们的帮助，伙计们。

根据你自己的经验，你怎么看？这真的是使这种过程更快的好方法吗？如果是或不是，为什么？有没有办法改进它？

谢谢，伙计们。

Answer 1

如果您知道该项目可能位于开头或结尾但不在中间，那么您提出的算法是好的，如果它可能在中间，则很糟糕，如果它同样可能在列表中的任何地方，则只是过于复杂。

一般来说，如果你有一个n个项目的未排序列表，那么你可能必须检查所有项目，这总是需要至少与n成正比的时间(这大致是符号"O(n("的意思(——除了从排序或部分排序的列表开始之外，没有办法解决这个问题。

在您的方案中，循环仅运行 n/2 次迭代，但它在每次迭代中所做的工作量大约是普通线性搜索(从一端到另一端(的两倍，因此它的总成本大致相等。

如果您确实有一个部分排序的列表(即，您有一些关于项目更有可能在哪里的信息(，那么首先从最有可能的位置开始是一个很好的策略。(假设您不经常查找根本不在列表中的项目，在这种情况下，没有任何帮助。

Answer 2

如果你从两端工作，那么当你要找的物品靠近中间时，你会得到最差的性能。不管你做什么，顺序搜索都是 O(n(。

如果要加快搜索列表的速度，则需要使用更好的数据结构，例如排序列表、哈希表或 B 树。