c - 在最坏的情况下，在排序的链表中搜索一个元素需要进行多少次比较？

Question

这是我大学数据结构和算法类(class)测验中的一道题

What is the number of comparisons required to search an element in a sorted linked list in the worst case?

这些是选项:

a. ceil (n/2)

b. ceil (log n)

c. n2

d. ceil ((log n) + 1)

e. n

根据答案正确答案是n。

但我是这样想的，在一个排序的链表中，搜索不需要遍历所有元素。它可以从当前节点跳转到第二个节点(如 curr->next->next 并保留前一个指针，如 prev = curr->next)并查看是否节点的key小于要搜索的key，

如果要搜索的键大于当前节点的键，我们重复这个。

否则，我们将搜索键与 prev->key 进行比较，如果它们相等，则找到该元素，否则该元素不存在于链表中

此方法将花费大约 (n/2) 次比较(如果与之前的比较则为 + 1)...所以答案应该是 ceil(n/2) 对吧？我说得对吗？

编辑:这是我上面提到的算法的c版本(链表的头部和要搜索的键是参数。skey是要搜索的键)

void search (struct node * head, int skey)
{
    struct node * curr = head,*prev = NULL;
    
    
    while(1)
    {
        if(curr==NULL)
        {
            if(prev!=NULL)
            {
                if(prev->key== skey)
                {
                    printf("FOUND");
                    break;
                }
                else
                {
                    printf("NOT FOUND");
                    break;
                }
            }
            else
            {
                printf("NOT FOUND");
                break;
            }
        }
        if(curr->key==skey)
        {
            printf("FOUND");
            break;
        }
        else if (curr->key < skey)
        {
            if(curr->next!=NULL)
            {
                prev=curr->next;
                curr=curr->next->next;
                
            }
            else
            {
                printf("NOT FOUND");
                break;
            }
        }
        else
        {
            if(prev!=NULL)
            {
                if(prev->key== skey)
                {
                    printf("FOUND");
                    break;
                }
                else
                {
                    printf("NOT FOUND");
                    break;
                }
            }
            else
            {
                printf("NOT FOUND");
                break;
            }
        }
        
    }
}

Answer 1

这是一种逐步遍历链表的方法，每个节点仅进行 2 次比较。

while( curr = head; curr != NULL && curr->skey != skey; curr = curr->next);

最坏的情况是 skey 不在链表中