2 votes 2 votes Why linked list not suitable for binary search? DS binary-search + – Anjali Raghu asked Apr 4, 2016 Anjali Raghu 810 views answer comment Share Follow See all 0 reply Please log in or register to add a comment.
Best answer 3 votes 3 votes There is no way to index the elements in the linked list which makes it unsuitable for binary search. srivivek95 answered Apr 4, 2016 • selected Jun 5, 2016 by Desert_Warrior srivivek95 comment Share Follow See all 2 Comments See all 2 2 Comments reply Arjun commented Apr 4, 2016 reply Follow Share We use binary search to reduce the search complexity to $O(\log n)$ but in a linked list to find the middle element itself takes $O(n)$. 8 votes 8 votes Anjali Raghu commented Apr 5, 2016 reply Follow Share Thanku 0 votes 0 votes Please log in or register to add a comment.
2 votes 2 votes Because nodes of linked list may or may not be present in the continuous memory location, so we can only use linear search while array occupies continuous memory location, so a binary search is possible. Nikhil Chaudhary answered Apr 16, 2016 Nikhil Chaudhary comment Share Follow See all 0 reply Please log in or register to add a comment.
0 votes 0 votes in binary search of an array we have the array size mentioned .Even if the size isn’t mentioned we can use an index and multiply it by 2 and we can easily find the end of the array in $O(\log n$) time.but if we want to find the end of the list or find the mid we need to traverse the entire linked list so its $O\left ( n \right )$and anything after that will not effect as it will be $O\left ( \ n \right )$+$O\left ( \log n \right )$ = $O\left ( \ n \right )$. So it is not suitable for linked lists. Psy Duck answered Jun 30, 2023 Psy Duck comment Share Follow See all 0 reply Please log in or register to add a comment.