c - 排序双向链表中的二进制与线性搜索

Question

我正在做一个使用双向链表进行图书馆管理的大学项目。双向链表在排序时保存书籍的 ID。

我曾尝试计算线性搜索与二分搜索在最坏情况下所用的时间。结果如下:

Binary search: 0.311ms
Linear search: 0.228ms
[Number of inputs(id's): 10000000]

我的问题:

尽管二分查找需要 O(logn) 次比较，但耗时更多是因为它需要 O(n) 次遍历，直到找到中间值。对于已排序的双向链表，有没有比繁琐的线性搜索更好的搜索算法？

我找到二分查找所需的中间值的实现:

struct node* middle(node* start, node* last) 
{ 
    if (start == NULL) 
        return NULL; 
    struct node* slow = start; 
    struct node* fast = start -> next; 
    while (fast != last) 
    { 
        fast = fast -> next; 
        if (fast != last) 
        { 
            slow = slow -> next; 
            fast = fast -> next; 
        } 
    } 
    return slow; 
} 

Answer 1

您的比较必须非常慢才能证明所有导航的合理性。就目前而言，我想不出比线性搜索更好的方法。如果您可以更改结构和 CRUD，您当然可以索引关键点(“A”从此处开始，“B”从此处开始等)，这将使您能够更好地猜测线性搜索的起点和方向。

我认为您会发现链表，无论是双重链表还是其他链表，都不是随机查找或按顺序更新的好选择。使用似乎更适合您在问题和评论中概述的情况的 B 树。