Order for binary searches

[Sherry Listgarten]

Ken's problem is basically: given an ordered array of T items, how long does
it take to find a particular item (which happens to be in entry N) using a
classical binary search. This is just asking how deep a value is in a
balanced binary tree.

A fully balanced binary tree has T = 2^r - 1 nodes, and say we number them
1, 2, 3, ..., T. This tree has depth r. Level 1 has one element, level 2 has
2, level 3 has 4, and so on, up to level r, which has 2^{r-1}. To get to
level r requires r values to be examined. So all we need to know is what
level a particular element (element N) is at. That's just r-p, where p is
the log2 of the largest power of 2 that divides N.

Example A: T=15, r=4. If N=8, then p=3, and r-p=1. And you'll note that 8 is
at the top of the balanced binary tree containing 15 elements, and so
requires one node to be examined.

Example B: T=15, r=4. If N is any odd number, then p=0, and r-p=4. This just
says that the odd numbers are at the leaves of the tree, and therefore four
nodes have to be examined.

Another way to think of it. Write N in binary. Read it from left (most
significant) to right, counting off each place until you get to the last 1
bit. That is the number of levels you'll have to look at.

For example A, N=1000 is at level 1.
For example B, N=....1 is at level r.

If T isn't exactly of the form 2^r - 1, then the tree isn't fully balanced,
and the number of comparisons depends on how the algorithm rounds things.

-- Sherry.

> -----Original Message-----
> From: fork-admin@xent.com [mailto:fork-admin@xent.com]On
> Behalf Of Wayne
> E Baisley
> Sent: Monday, November 12, 2001 7:12 PM
> To: Rodent of Unusual Size
> Cc: fork@xent.com
> Subject: Re: Order for binary searches
>
>
> > > 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
>
>
> http://xent.com/mailman/listinfo/fork