Order for binary searches

[Jeff Barr]

Isn't this really the same as a binary search, changing only
the fact that the terminal condition is:

	(cell[n] == 1 && cell[n+1] == 0)

?

The value being searched for just happens to span two cells.
There is exactly one place where the cells stop being 1's
and start being 0's, right? The array is always:

	1 ..... 1 0 ...... 0

So this is just a standard binary search, complexity-wise.

Jeff;

-----Original Message-----
From: fork-admin@xent.com [mailto:fork-admin@xent.com] On Behalf Of
Rodent of Unusual Size
Sent: Monday, November 12, 2001 5:42 PM
To: Kragen Sitaker
Cc: fork@xent.com
Subject: Re: Order for binary searches


* On 2001-11-12 at 20:31,
  Kragen Sitaker <kragen@canonical.org> excited the electrons to say:
> 
> Ken Coar writes:
> > What expression will tell me the maximum number of samples
> > required to find that last 1 cell?  E.g., n log(base 2) of t
> > (or whatever)..
> 
> It's about 1 + floor(log base 2 of t), but I'm not sure what it is
> exactly.  I think it's exactly the same worst-case behavior as
standard
> binary search.

I think you and one of the other respondents didn't understand
my question.  I amd NOT looking for the maximum number of
samples I need to take to ever find a cell.  I *know* which
cell I want, and the thing I'm trying to determine is how many
samples I need to take to find it.

Put it another way: Expressions involving only t are invariant
with regard to n, which obviously is useless except as a worst-case
quantity.

Try an example:

1. If t=137, and n=89, how many samples will need to be
   taken to determine that cell 89 is the last containing 1?
   What expression describes that for all n?

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.
-- 
#ken	P-)}

Ken Coar, Sanagendamgagwedweinini  http://Golux.Com/coar/
Author, developer, opinionist      http://Apache-Server.Com/

"All right everyone!  Step away from the glowing hamburger!"


http://xent.com/mailman/listinfo/fork