为什么不能在已排序的链表中进行二进制搜索？ [英] Why binary search is not possible in sorted linked list?

问题描述

是否可以在分类的链表中使用二进制搜索来搜索元素？
如果不可能，那么问题是为什么不可能？

Is it possible to search a element with binary search in sorted linked list? If it is not possible then the question is "why it is not possible"?

推荐答案

我觉得写错了这个答案是因为我暗中怀疑这是一项家庭作业。但是，由于与评论中的某些人进行了讨论，我认为其他人可能会对此感兴趣。

I feel wrong writing this answer because I have a sneaky suspicion that it's a homework assignment. However, due to discussions with some people in the comments, I think it may be of interest to other people.

对有序数组进行二进制搜索可以得出O的结果（log N）比较和O（1）内存利用率。在排序的数组上进行线性搜索会为我们提供O（N）比较和O（1）内存利用率的结果。

Binary search on a sorted array gives us the result in O(log N) comparisons and O(1) memory utilization. Linear search on a sorted array gives us the result in O(N) comparisons and O(1) memory utilization.

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

Beyond the normal memory and comparison measurements, we also have the idea of traversal steps. This is important for data structures with no random access. For example, in a linked list, to get to element j from the head, we would need to take j steps forward. These steps can happen without any comparison. As pointed out in the comments, the cost for making a traversal step may be different from the cost for making a comparison. A traversal step here translates to a memory read.

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

The question is what happens when our data structure is a sorted singly linked list? Is it worth doing binary search?

要解决此问题，我们需要查看排序的单链接列表上二进制搜索的性能。代码看起来像这样：

To address this, we need to look at the performance of binary search on a sorted singly linked list. The code looks like this:

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 是排序的单链接列表中的头节点。

The function binarySearch returns the node with element equal to or just greater than v. The parameter n is the head node in a sorted singly linked list.

很明显，外循环迭代O（log N）次其中N =列表的大小。对于每个迭代，我们进行2次比较，因此比较的总次数为O（log N）。

It is clear that the outer loop iterates O(log N) times where N = size of the list. For each iteration, we make 2 comparisons, so the total # of comparisons is O(log N).

遍历步数为 right = right-> next; 被执行，即O（N）。这是因为内层循环的迭代次数在外层循环的每次迭代中减少一半，因此N / 2 + N / 4 + ... + 1 = N（正负摆动空间）。

The number of traversal steps is the number of times right = right->next; gets executed, which is O(N). This is because the # of iterations in the inner loop decreases by half at each iteration of the outer loop, so N/2 + N/4 + ... + 1 = N (plus or minus some wiggle room).

内存使用率仍为O（1）。

Memory usage is still O(1).

相反，通过排序的单链接列表进行的线性搜索为O（ n）遍历步骤，O（n）比较和O（1）内存。

In contrast, linear search through a sorted singly linked list is O(n) traversal steps, O(n) comparisons, and O(1) memory.

那么在单链表上进行二进制搜索值得吗？答案是几乎总是是，但不是完全如此。

So is it worth doing binary search on a singly linked list? The answer is almost always yes, but not quite.

不管计算成本如何，如果我们要寻找的元素是列表中的第二个元素？线性搜索需要1步和1个比较。二进制搜索需要〜N个步骤，〜log N个比较。现实不是很清楚。

Disregarding the cost to count, what happens if the element we are looking for is the 2nd element in the list? Linear search takes 1 step and 1 comparison. Binary search takes ~ N steps and ~log N comparisons. Reality isn't so clear.

所以这里是摘要：

排序数组

 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。我们永远不必前进或后退。这个想法甚至都没有道理。

Although, technically, the # of required traversal steps is 0 for sorted arrays. We never have to step forward or backwards. The idea doesn't even make sense.

排序的单链接列表

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

这些是最坏的运行时间。但是，玻璃杯可能并不总是半空的：p

And these are worst case run time. However, the glass may not always be half empty :p

这篇关于为什么不能在已排序的链表中进行二进制搜索？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！