Линейный и двоичный поиск списка с использованием массивов и связанного списка

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. 

Вы не можете получить третий элемент за постоянное время. В двоичном поиске вы должны перейти к элементу всякий раз, когда захотите. Рассмотрим, что ваш связанный список - 1 миллион узлов. Есть ли способ перейти на 500 000-й узел в постоянное время? Если ответ «да», в любой реализации связанного списка вы можете найти его в 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;