I know that the Binary Search algorithm has a Big-O of logN,but does this hold t

Question

I know that the Binary Search algorithm has a Big-O of logN,but does this hold true when the search is implemented with adoubly linked list instead of an array?

I want to say yes because the part of the linked list that you willtraverse is going to be halved after each data comparison. However, you still need to traverse a lot more elements in a linkedlist than a data structure with random access like an array. Is this difference so small that it really doesn't effect thealgorithms efficiency?

Any help would be greatly appreciated. :)

Explanation / Answer

With double Linked list, the binary search algorithm does not takeO(log N) In double linked list we cannot access the elements randomly likein array ( we have to traverse to the element in order tocompare) For the binary search algorithm to compare the median element everytime, the list has to be traversed to the middle. Then only we cancompare the middle element . Double linked list takes O(N) time for binary search.

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.