A Simple C Question

[Ecko]

We'll a very simple C question here related with data structures

I want to know if Binary Search can be done in Linked List
An explanation will be highly appreciated

 

[iq6886]

Yes Binary search can be done using linked list...

but we simply don't coz the complexity of binary search using linked list is O(nlgn) and not O(lgn ) as in arrays..
let me explain you why this..

basically the increase in complexity is because of the added complexity to seeking to any element which is constant when using array( when we need to reach middle we just index it in array , but in linked list we need to reach it by traversing the linked list ).

so we need to tranverse linked list for every step of binary search or log n times.

I guess i explained it properly enough....

 

[Ecko]

Thanx a lot dude
Got it
BTW what's this

the complexity of binary search using linked list is O(nlgn) and not O(lgn ) as in arrays..

 

[Faun]

that big O notation Scary stuff, not anymore.

 

[srinivasa.s]

How is the complexity (n log n)? Its still linear - O(n). The worst case complexity of even linear search is O(n). This cannot be any worse! Basically, the search will not be called "binary search" if its done on lists

 

[iq6886]

^ it will still be called binary search beacoz of the concept whtr done using arrays or linked list or any other data type of ur choice..

and about the complexity , you can easily find it out to be O(nlgn) by solving the equation
T(n)=T(n/2) + O(n) ( not so sure about the equation though.. need to chk tht)