arrays - 使用数组和链表对列表进行线性和二进制搜索

Question

到目前为止，在数据结构中，我已经研究了使用数组的列表和使用指针的链表（单、双和循环）。大纲中的下一件事是线性和二进制搜索。我找到了列表和链表的线性搜索的例子。对于二进制搜索，我在使用数组的列表中找到了一个示例，但没有链接列表（单、双和循环）的示例。
1）我想知道二分查找不能适用于任何类型的链表？
2）同样在单链表的线性搜索中，我看到了这段代码

if (ptr->data = = SearchElement){
indexPtr = ptr;
return indexPtr;}

在这种情况下，当它找到元素时，它会返回指针的地址，是否正确？没有初始化，indexPtr所以我认为它也是节点类型指针。

Answer 1

没有办法使用链表进行二进制搜索。想象以下是您的链接列表。

1->2->3->4->5->6 and you are searching for 1.

您无法在恒定时间内获得第三个元素。在二进制搜索中，您必须随时跳转到某个元素。考虑您的链表是 100 万个节点。有没有办法在恒定时间内到达第 500,000 个节点？如果答案是肯定的，那么在任何链表的实现中，你都可以在 O(log(n)) 中找到它。

检查这个和这个问题和答案。

线性搜索代码应该是这样的。

ptr = head;
while (ptr-> next != null)
    if(ptr -> data == searchedElement)
        return ptr;

它将返回指向匹配节点的指针。

已经有一段时间了，我还没有检查，但应该是这样的。

cout << "address of ptr: " << &ptr << " address of node " << ptr << " value inside the node " << *ptr << endl;