Why can;t we use binary search on a Linked List if all the elements of Linked List are in sorted order ?

4 votes

Linked Lists are not suitable for _____.

A. Binary Search

B. Polynomial Manipulation

C. Insertion

D. Radix Sort

A. Binary Search

B. Polynomial Manipulation

C. Insertion

D. Radix Sort

closed as a duplicate of:
GATE1994-1.17, UGCNET-Sep2013-II: 32

4 votes

Best answer

0

Why can;t we use binary search on a Linked List if all the elements of Linked List are in sorted order ?

1

In sorted order, still we have to traverse to the middle of linked list which takes O(n/2) which is O(n) only .

but, this can be made O(log n) by augmenting linked list with extra pointers like DLL, called skip list so that we can move in both the directions. which can give O(log n ) but not always, bcoz still worst is O(n).

but, this can be made O(log n) by augmenting linked list with extra pointers like DLL, called skip list so that we can move in both the directions. which can give O(log n ) but not always, bcoz still worst is O(n).

0

@kapil then why do we use binary search in sorted array ? we use the same concept there rt ? we can apply binary search on sorted array to get down the complexity upto O(logn) .don't we need to traverse there ?