first of all, it's all nomenclature, and i don't want to make a whole thing out of this, but binary search requires that you can randomly go left or right every time you subdivide the (linear) ordering, not that you can randomly index to any element.
EDIT
also, perhaps against better judgment, i'm going to throw a possibly inflammatory remark out there and say that the big-O thing is really not that difficult or important (although i suppose that it's important that it not be difficult). what i can see taking some skill/experience (which i totally don't have) is knowing a bunch of algorithms and being able to consider the time/space tradeoffs of the algorithms you already know quickly. being able to prove the time-complexity of some new algorithm is good, but, sadly, perhaps, i don't think most companies hire people to do that.
i wish people would comment when they downvote. i made the final comment already knowing (and stating!) that it might rub someone the wrong way but hoping that it might provoke discussion. it's a reasoned and reasonably-informed comment, not just noise-making or an attempt to troll. downvoting without comment in that situation doesn't really further the discussion.
of course, when there are two or three items left, choosing between left and right is the same as choosing an arbitrary index. that's nomenclature. whether you follow the rote textbook definition and do that indexing up front or delay it until you've paired down your possibly-large list into a manageable (whatever that might mean for the problem domain you're dealing with) size, it's still pretty much the same algorithm.
and since you're imagining rather than being certain, that means people continue to downvote without comment, and i continue to cheerily object to that.
