Order for binary searches

[Wayne E Baisley]

> > Let's ignore the contents.  Given t elements, how many samples
> > does it take to arrive at n, where 0 <= n <= t?
> >
> > Maybe that's clearer.. I had trouble describing this to someone
> > else to-day; he kept telling me log2(t), also.. as in 'it will never
> > take more than log2(t) tries to find a cell.'  Not what I want.
> 
> I think what you're asking for is ...
> 
> log2 (|t/2 - n|)

Which is to say that everytime you double n's distance from the
midpoint of t's searchspace, you add a comparison test.  Of course,
this only works if 'distance from the midpoint' is measured in
searches, so the encoding would have to be some kind of Grey code.
Which doesn't match your problem.  Nevermind.

I think you're still stuck with O (log2 (t)).

Cheers,
Wayne