線性和二進制搜索列表使用數組和鏈表

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. 

你不能在常量時間獲得第3個元素。在二分查找中，您必須隨時跳轉到某個元素。考慮一下你的鏈表是100萬個節點。有沒有一種方法可以在第50萬個節點上持續運行？如果答案是肯定的，那麼在任何鏈接列表的實現中，你都可以在O（log（n））中找到它。

檢查this和this問題&答案。

線性搜索代碼應該是這樣的。

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;