Solution Review: Binary Search on Singly Linked List

Solution

Performing Binary Search requires figuring out the middle element. Binary Search is efficient for arrays because arrays are contiguous and accessing the middle index between two given indices is easy and can be done in $O(1)$.

Memory allocation for the singly linked list is dynamic and non-contiguous, which makes finding the middle element difficult. The given algorithm presents one way to perform the binary search on a Singly Linked List.