[mplspm]: In a sorted list

[Troy Johnson]

Fun!

>>>>>START>>>>>
#!/usr/local/bin/perl -w

my @array = (aa..yy);

foreach $s (qw(cc gg mm aa yy zz))
{
	my $rv = findit($s, \@array);
	print "debug: \$rv = $rv\n";
}

sub findit
{
        my $string = shift;
        my $sar = shift;	# sorted array reference
        my $try = my $interval = my $size = scalar @{$sar};
        my $dir = -1;
        my %seen = ();
        my $done = 0;
        my $found = 0;
        
        while (not $done)
        {
        	$interval = int($interval / 2) || 1;
        	$try += $dir * $interval;
		if ($try < 0 or $try >= $size)
        	{
        		$done = 1;
        		next;
        	}
        	$dir = $string cmp $sar->[$try];
		print "debug: $size  $interval  $try  $dir  $string $sar->[$try]\n";
        	if (not $dir)
        	{
        		$found = 1;
        		$done = 1;
        		next;
        	}
        	if (exists $seen{$sar->[$try]})
        	{
        		$done = 1;
        		next;
        	}
        	$seen{$sar->[$try]} = undef;
        }

	return $found;
}
<<<<<<END<<<<<<

Probably not super, but fun... :-)

Thomas Eibner wrote:
> 
> On Thu, Mar 21, 2002 at 10:07:22PM -0600, Josh Aas wrote:
> > Hey MPM,
> >     If I have an alphabetically sorted array of strings (containing up to 2
> > million strings), and I want to find out if any strings in that array equal
> > a certain string (yes or no, not how many), what is the fastest way to do
> > that search? This seems basic to me, I just can't come up with the answer
> > and I have an hour to do so. Thanks a lot!
> 
> An "easy" way to do it would simply be to grep on the array, but probably
> not the fastest way to do it.
> 
> if (grep {/^thestring$/} @sorted_array) { # match! }
> 
> But since you say you have it sorted alphabetically, you might want to do
> something like taking the number of entries, taking the middle element
> out and comparing it by the first letter to see wheter it was close to the
> string or not and then continue with moving half way to one side.. just an
> idea anyway.


--------------------------------------------------
Minneapolis Perl Mongers mailing list

To unsubscribe, send mail to majordomo at pm.org
with "unsubscribe mpls" in the body of the message.