Menu
This earlier question talks about doing binary search over a doubly-linked list in O(n) time. The algorithm in that answer work as follows:
This works perfectly well for a doubly-linked list because it's possible to move both forwards and backwards, but this algorithm wouldn't work in a singly-linked list.
Is it possible to make binary search work in time O(n) on a singly-linked list rather than a doubly-linked list?
516
In effect, binary search on a linked list can be implemented in O(n) by doing a linear search ... the name doesn't mandate what it actually does. The advantage is that while it does O(n) work traversing the list, it only makes O(log n) comparisons.
The time complexity of the Linear search is O(n). Another approach to perform the same task is using Binary Search. Binary Search Approach: Binary Search is a searching algorithm used in a sorted array by repeatedly dividing the search interval in half.
To search a linked list, you are going to iterate over each item in the list. The most time this will take, will be T(n) where n is the length of your list.
In any binary search tree the time complexity taken is O(h), where h is the height of the tree.. Since it is given that tree is balanced binary search tree so searching for an element in worst case is O(logn).
It's absolutely possible to make this work. In fact, there's pretty much only one change you need to make to the doubly-linked list algorithm to make it work.
The issue with the singly-linked list case is that if you have a pointer to the middle of the list, you can't go backwards to get back to the first quarter of the list. However, if you think about it, you don't need to start from the middle to do this. Instead, you can start at the front of the list and walk to the first quarter. This takes (essentially) the same amount of time as before: rather than going backward n / 4 steps, you can start at the front and go forwards n / 4 steps.
Now suppose you've done the first step and are at position n / 4 or 3n / 4. In this case, you're going to have the same problem as before if you need to back up to position n / 8 or position 5n / 8. In the case that you need to get to position n / 8, you can start at the front of the list again and walk forward n / 8 steps. What about the 5n / 8 case? Here's the trick - if you still have pointer to the n / 2 point, then you can start there and walk forwards n / 8 steps, which will take you to the right spot.
More generally, instead of storing a pointer to the middle of the list, store two pointers into the list: one at the front of the range where the value might be and one in the middle of the range where the value might be. If you need to advance forward in the list, update the pointer to the start of the range to be the pointer to the middle of the range, then walk the pointer to the middle of the range forward halfway to the end of the range. If you need to advance backward in the list, update the pointer to the middle of the range to be the pointer to the front of the range, then walk forwards halfway.
Overall, this has the exact same time complexity as the doubly-linked case: we take n / 2 steps, then n / 4 steps, then n / 8 steps, etc., which sums up to O(n) total steps. We also only make O(log n) total comparisons. The only difference is the extra pointer we need to keep track of.
Hope this helps!
167
The comparison takes O(1), what takes more time is traversing the nodes. So even if you hold pointers to n/2, n/4 and 3n/4 - the time that'll take you to find it will remain O(n).
Further, if you start from the middle and go back(or forward) you might as well compare along the way cause it takes the same amount of time to do another comparison: O(1).
To sum up:
Running a binary-search on a linked list makes no sense unless the linked-list is backed up by an array (ArrayList) which allows direct access to its elements in O(1).
38
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
