为什么在排序链表中无法进行二进制搜索？

Question

是否可以在已排序的链表中搜索带二进制搜索的元素？如果不可能那么问题是"为什么不可能"？

Answer 1

写这个答案我觉得不对,因为我有一个偷偷摸摸的怀疑,这是一个家庭作业.但是,由于在评论中与一些人讨论,我认为其他人可能会感兴趣.

对排序数组进行二进制搜索可以得到O(log N)比较和O(1)内存利用率的结果.对排序数组进行线性搜索可以得到O(N)比较和O(1)内存利用率的结果.

除了正常的记忆和比较测量,我们还有遍历步骤的想法.这对于没有随机访问的数据结构很重要.例如,在链表中,要从头部获取元素j,我们需要向前迈出j步.这些步骤可以在没有任何比较的情 正如评论中所指出的,进行遍历步骤的成本可能与进行比较的成本不同.这里的遍历步骤转换为内存读取.

问题是当我们的数据结构是一个排序的单链表时会发生什么？值得做二分搜索吗？

为了解决这个问题,我们需要在排序的单链表上查看二进制搜索的性能.代码如下所示:

struct Node {
        Node* next;
        int value;
};

Node* binarySearch(Node* n, int v) {
        if (v <= n->value) return n;

        Node *right, *left=n;
        int size = count(n);

        while (size > 1)
        {
                int newSize = (size / 2);

                right = left;
                for (int i = 0; (i < newSize) && (right->next!=nullptr); i++)
                        right = right->next;

                if (v == right->value) return right;
                else if (v > right->value) left = right;

                size -= newSize;
        }

        if (right && (v < right->value)) return right;
        else if (right->next) return right->next;
        else return nullptr;
}

函数binarySearch返回元素等于或大于v的节点.参数n是排序的单链表中的头节点.

很明显,外循环迭代O(log N)次,其中N =列表的大小.对于每次迭代,我们进行2次比较,因此比较的总数为O(log N).

遍历步数是right = right-> next的次数; 被执行,即O(N).这是因为在外循环的每次迭代中,内循环中的迭代次数减少了一半,因此N/2 + N/4 + ... + 1 = N(加上或减去一些摆动空间).

内存使用率仍为O(1).

相反,通过排序的单链表进行的线性搜索是O(n)遍历步骤,O(n)比较和O(1)存储器.

那么值得在单链表上进行二分搜索吗？答案几乎总是肯定的,但并不完全.

无视计算成本,如果我们要查找的元素是列表中的第二个元素会发生什么？线性搜索需要1步和1比较.二进制搜索需要~N步和~log N比较.现实并不那么清楚.

所以这是摘要:

排序数组

 Binary: O(log N) comparisons, O(1) memory, O(log N) traversal steps
 Linear: O(N) comparisons, O(1) memory, O(N) traversal steps

虽然从技术上讲,排序数组所需的遍历步数为0.我们永远不必前进或后退.这个想法甚至没有意义.

排序单链表

 Binary: O(log N) comparisons, O(1) memory, O(N) traversal steps
 Linear: O(N) comparisons, O(1) memory, O(N) traversal steps

这些都是最糟糕的运行时间.但是,玻璃可能并不总是半空:p