Re^2: Check word presence WITHOUT hashes or grep

++ IIRC from a math class back in the Cambrian, binary search is unbeatable on sorted data. Given a 500,000 word dictionary you will never have to do more than, let's see...

my $lookups = 0;
my $words = 500_000;

while ( $words > 1 )
{
    $words /= 2;
    $lookups++;
}

print $lookups, "\n";
[download]

...19 lookups -- meaning comparisons with some combination of lt, gt, ge, le, eq.

Comment on Re^2: Check word presence WITHOUT hashes or grep Select or Download Code

Replies are listed 'Best First'.
Re^3: Check word presence WITHOUT hashes or grep by gojippo (Novice) on Apr 30, 2008 at 05:43 UTC
Thank you all for your help. You aren't perl monks, but perl gods ! Just a question to my mother, what does the `$words /= 2;` part mean ? Divide $words into 2, to get 250 000 ?	[reply] [d/l]
Re^4: Check word presence WITHOUT hashes or grep by Your Mother (Archbishop) on Apr 30, 2008 at 05:49 UTC
:) That's right. `/=` is the operator for "divide yourself" or "divide in place." There's probably a better or more technical term. There are plenty more where that came from. See `perldoc perlop` for more fun.	[reply] [d/l] [select]