25 votes 25 votes In the worst case, the number of comparisons needed to search a single linked list of length $n$ for a given element is $\log n$ $\frac{n}{2}$ $\log_2 {n} - 1$ $n$ DS gatecse-2002 easy data-structures linked-list + – Kathleen asked Sep 15, 2014 • retagged Jul 1, 2017 by Silpa Kathleen 14.9k views answer comment Share Follow See 1 comment See all 1 1 comment reply viral8702 commented Jul 28, 2023 reply Follow Share Why people are saying that “Binary search is not efficient on linked list as it takes O(n) time to search in LL”, I mean it’s correct but in question it’s nowhere mentioned that linked list is sorted, so anyway Binary search is not applicable here! 0 votes 0 votes Please log in or register to add a comment.
Best answer 29 votes 29 votes A & C are not correct as we can not do binary search efficiently {it takes O(n)} in Linked list. B seems like average case, be we are asked for worst case. Worst case is we do not find the element in list. We might end up searching entire list & comparing with each element. So, answer -> (D). $n$ Akash Kanase answered Nov 24, 2015 • edited Oct 29, 2022 by Abhrajyoti00 Akash Kanase comment Share Follow See all 5 Comments See all 5 5 Comments reply Show 2 previous comments bharti commented Sep 5, 2017 reply Follow Share @reena_kandari more than n is only possible when you apply binary search . otherwise , by linear method it will take n 0 votes 0 votes vishalshrm539 commented Nov 23, 2017 reply Follow Share worst case is not just element is not found, if searched element is the last element then also N comparision are required...isn't it..? 1 votes 1 votes eyeamgj commented Oct 1, 2018 reply Follow Share SAYING WE CANT DO BINARY SEARCH IS WRONG WE CAN DO BUT IT IS NOT EFFICIENT TO DO BINARY SEARCH IN LINKED LIST IT GIVES ALMOST O(N) TC 6 votes 6 votes Please log in or register to add a comment.
9 votes 9 votes Binary search algorithm is based on the logic of reducing your input size by half in every step until your search succeeds or input gets exhausted. Important point here is "the step to reduce input size should take constant time". In case of an array, it's always a simple comparison based on array indexes that takes O(1) time. But in case of Linked list you don't have indexes to access items. To perform any operation on a list item, you first have to reach it by traversing all items before it. So to divide list by half you first have to reach middle of the list then perform a comparison. Getting to middle of list takes O(n/2)[you have to traverse half of the list items] and comparison takes O(1). Total = O(n/2) + O(1) = O(n/2) So the input reduction step does not take constant time. It depends on list size. hence violates the essential requirement of Binary search. thts why d is the answer only in worst case set2018 answered Aug 12, 2017 set2018 comment Share Follow See all 0 reply Please log in or register to add a comment.
8 votes 8 votes Since, It is not possible to do a Binary search in Linked List, the Only solution is linear search so its O(n). Prasanna answered Aug 21, 2015 Prasanna comment Share Follow See all 3 Comments See all 3 3 Comments reply srestha commented May 11, 2017 reply Follow Share But is it asked about complexity? It asked about number of comparison only. 0 votes 0 votes talha hashim commented Aug 29, 2019 reply Follow Share Binary search is possible on linked list but it is not efficient than linear search so we avoid it and use linear search 0 votes 0 votes Prateek.py commented Jul 10, 2020 reply Follow Share not impossible but time consuming 0 votes 0 votes Please log in or register to add a comment.
4 votes 4 votes There are n elements so Log2n is not the case in single linked list because binary search not possible so option A and C is wrong In worst case there are n comparisons so option D is right Rishi yadav answered Oct 4, 2017 Rishi yadav comment Share Follow See 1 comment See all 1 1 comment reply sutanay3 commented Jul 18, 2018 reply Follow Share In which case searching in single linked list takes n/2- when we get an element in middle of the list. 0 votes 0 votes Please log in or register to add a comment.