Can we do a Binary search on a linked list ?

Of-course we can do a binary search on the linked list, But We have to think, Is is efficient. Binary Search is fast and effiecient in to array beacuse of constant access time of element from the array, like we can get middle of the array just by saying array[middle], But If we want to do the same thing in to link list, for this we have to write our own algorithm to find the middle element in to the linked list. In a linked list it is not possible to find the middle element in a constant time. One solution to the inefficiency of getting the middle of the linked list during a binary search is to have the first node contain one additional pointer that points to the node in the middle. Decide at the first node if you need to check the first or the second half of the linked list. Continue doing that with each half-list

 

1,655 total views, 5 views today

Leave a Reply