I mean, yeah, binary search is sublinear, but the data has to be ordered into a binary search tree to be able to use it, which has a much more familiar (non-sub-linear) runtime.

I have to assume the reason for the article wasn't to talk about the runtime of algorithms that operate on data that's already in a partially solved state.