Re: Algorithms in C - Robert Sedgewick

arnuld wrote:
On Wed, 09 Sep 2009 10:39:31 +0000, Richard Heathfield wrote:

In <ln7hw8zinh.fsf@xxxxxxxxxxxxxxx>, Keith Thompson wrote:
The average *successful* search
Er, quite so. I should have pointed that out. Thank you.

By that you mean the worst case successful search (20th comparison) or a successful search which is not worst case( e.g. 10th, 15th or even 3rd comparison) ??

Aha! Here's a perfect example of the kind of "Why
mathematics matters" issue you asked about earlier. No
search, successful or unsuccessful, will take more than
twenty comparisons. Some "lucky" successful searches
will take fewer, by happening to hit on the desired key
while the "active" interval is still relatively wide.
One particularly lucky successful search will find its
key on the very first comparison! How does the "luck
factor" skew the average? Is the effect significant, or
is it negligible? *That's* the kind of question that faces
a programmer often and often again. Care to have a go?


S

P

O

I

L

E

R



S

P

A

C

E


One way to tackle the problem is to set up one of those
recursions you seem to dread. Let's work "forward," following
the comparisons as they're made. The very first comparison in
an array of N elements lands on the desired key with probability
1/N. Otherwise (with probability 1-1/N) it misses, but leaves
you with only (N-1)/2 array locations still to be searched.
Letting C(N) be the average number of comparisons to find a
key in an array of size N (we're assuming a successful search),
we've got

C(N) = 1 * (1/N) + C((N-1)/2) * (1 - 1/N)

.... and if you can solve this recursion, you're all set. (The
decision of whether to start with C(1)=0 or C(1)=1 depends on
how sure you are that the key is actually present.)

By the way, the recursion I've shown is not quite right,
as it glosses over one crucial detail. Can you spot it? (Hint:
is N even or odd?)

Another way to attack the problem is to visualize the search
as a binary tree. The root node is the first array slot you
compare against. The left sub-tree is rooted at the slot you
check second if the original comparison comes out <, and the right
sub-tree starts at the second-compared slot if the first comparison
comes out >, and so on through the third, ..., twentieth comparison.
There are N nodes in the tree altogether. The number of comparisons
you make to arrive at any particular node K is one plus K's distance
from the root of the tree. So the average number of comparisons
is the tree's "internal path length," divided by N, plus one. If
you know something about the mathematics of trees, you are once
again all set.

--
Eric Sosman
esosman@xxxxxxxxxxxxxxxxxxxx
.

Relevant Pages

  • Re: ifstream::get() surprise
    ... Also note that 'get' is an unformatted input function. ... stores all characters into 'buf' and leaves the ... No such thing as 'successful read of zero characters.' ... null character into the next successive location of the array. ...
    (comp.lang.cpp)
  • Extraction of single subarrays from multidimensional array
    ... picking out single subarrays ... from a multidimesional array. ... by iteration over array ss. ...
    (comp.lang.ruby)
  • RE: IDsObjectPicker AttributesToFetch mystery
    ... On return pvarFetchedAttributes holds an array of variants in the same order ... as the attributenames directory. ... > trying to retrieve the objectSID from this call. ... > have been successful only when no additional attributes are requested. ...
    (microsoft.public.windows.server.active_directory)
  • Re: Converting Bitmap into 2D-Array
    ... First problem here: VC6 is really old, unsupported by the vendor and far ... and convert it to a 2D array where each element represents one of the ... struct bitmap { ... operation will be successful. ...
    (microsoft.public.vc.language)
  • Re: linux-next: manual merge of the trivial tree with the net tree
    ... "successful" and variants in comments") from the trivial tree. ... Subject: NET: Fix misspelling of "successful" and variants in comments. ... If the driver can't succesfully parse the BIST output, ...
    (Linux-Kernel)