[a1369209993]

Also they're just straightforwardly wrong. For example, binary search works on a array, or on a predicate like \x->(x*x <= 2.0), or on a hash table with contiguous integer indexes, or even on a linked list. Of course it works very badly on a linked list (worse than linear scanning unless the comparison is ruinously expensive), but they didn't say "An algorithm always only works properly on a certain data data structure.".

[eska]

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]

> 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]

Having random access means that it‘s O(1).

[a1369209993]

No, 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]

At 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.