使用数组和链表线性和二分搜索列表

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((中找到make it。

检查这个和

这个问题和答案。

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

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;