3 ms·
A binary search on a linked list is a different algorithm than on a a sorted array (which is different from a generic array). In this case linked lists don’t ha
by eska 3y ago
A binary search on a linked list is a different algorithm than on a a sorted array (which is different from a generic array). In this case linked lists don’t have random access for example. So binary search on a linked list is actually not possible.
- a1369209993 3y ago> linked lists don't have random access `list.get_nth(n)` has O(N) runtime, as does `list.length()`, so binary search is actually completely possible, with runtime O(N^2) (aka "works very badly"). (Fair point that all four data structures need to be sorted, though, although ideally that would go without saying, since it's kind of inherent in what binary search is.)
- eska 3y agoHaving random access means that it‘s O(1).
- a1369209993 3y agoNo, having efficient random access means that it's O(1). That just usually goes without saying, because anything that has access at all can be made to have inefficient random access. But in this case, the fact that it's (necessarily) inefficient is the point: binary search works very badly on a linked list, and you shouldn't actually use that algorithm with that data structure even though you technically can. Conversely, using the same algorithm on a (sorted) array, (monotonic) predicate, or (sorted,contiguously-keyed) hash table works fine, even though those are three different data structures.
- eska 3y agoAt that point the definition would be useless. It’s not the definition I’ve seen during my CS education, in papers and even what’s written about it on Wikipedia.