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