Perl Guru Forums: Perl Programming Help: Beginner: Binary Search Help please

CGI/Perl Guide | Learning Center | Forums | Advertise | Login

Site Search: in


	MAIN INDEX	SEARCH POSTS	WHO'S ONLINE	LOG IN

Home: Perl Programming Help: Beginner:
Binary Search Help please

kev670
Novice

Oct 21, 2009, 2:08 PM

Post #1 of 16 (879 views)

Binary Search Help please	Can't Post

I'm writing a larger program and am trying to implement a binary search. In this test program the sub reads in a preset array with 5 elements. the program should ask for a name and return 1 if the name is found and 0 if it isn't, but unfortunatly it only reads back 1 for some of the elements and i cant figure it out. can you help please

Code

 #!/usr/bin/perl  
use strict;  
use warnings;  
  
  
my @namesArray  = ("bill", "cill", "dill", "fill", "zzzz");  
  
	print "\tName: ";  
  
	my $name;  
  
	$name = <STDIN>;  
  
	chomp($name);  
  
	my $i = &binarySearch ($name,@namesArray);  
  
	print "$i";  
  
sub binarySearch  
{  
my ($nameHolder, @namesArray) = @_;    
my $high=@namesArray-1;  
  
    my $low = 0;  
  
  
  
	while ($low <= $high)   
	{  
  
		my $mid = ($low + $high)/2;  
  
		if  (($namesArray[$mid] lt $nameHolder))  
		{   
  
  
			$low  = $mid + 1;	  
  
		}   
  
		elsif (($namesArray[$mid] gt  $nameHolder))  
		{  
			#print "hi tere 2";  
  
			$high = $mid - 1;  
  
		}  
		else  
		{  
			return 1;  
		}  
	}   
  
     return 0;  
  
}

(This post was edited by kev670 on Oct 21, 2009, 4:25 PM)

toolic
User

Oct 21, 2009, 4:02 PM

Post #2 of 16 (871 views)

Re: [kev670] Binary Search Help please [In reply to]	Can't Post

Are you aware that you are performing numeric comparisons of strings? For example:

Code

if  (($namesArray[$mid] lt $nameHolder))

While it is legal, I suspect it is not what you want to do.

FishMonger
Veteran

Oct 21, 2009, 4:09 PM

Post #3 of 16 (868 views)

Re: [kev670] Binary Search Help please [In reply to]	Can't Post

Is your actual data strings or numbers?

kev670
Novice

Oct 21, 2009, 4:22 PM

Post #4 of 16 (865 views)

Re: [FishMonger] Binary Search Help please [In reply to]	Can't Post

It reads in strings as defined by the array at the biginning. The user then inputs his own string and the program is supposed to see if the string the user entered has a match or not in the array

FishMonger
Veteran

Oct 21, 2009, 4:28 PM

Post #5 of 16 (862 views)

Re: [kev670] Binary Search Help please [In reply to]	Can't Post

This is clearly a homework assignment, so I can't/won't provide a better solution, but the script as written gave me the proper results for each element in the array.

Can you post an example that doesn't work as expected?

kev670
Novice

Oct 21, 2009, 4:34 PM

Post #6 of 16 (859 views)

Re: [FishMonger] Binary Search Help please [In reply to]	Can't Post

It doesn't fully work for me.

When i enter "cill" or "zzzz" the program returns 0 meaning it didnt match these inputs to the string. i dont understand why it doesn't, because the program looks right to me

(This post was edited by kev670 on Oct 21, 2009, 4:35 PM)

FishMonger
Veteran

Oct 21, 2009, 4:39 PM

Post #7 of 16 (855 views)

Re: [toolic] Binary Search Help please [In reply to]	Can't Post

In Reply To

Are you aware that you are performing numeric comparisons of strings? For example:

Code

if  (($namesArray[$mid] lt $nameHolder))

While it is legal, I suspect it is not what you want to do.

Actually, in this case it is exactly what is needed and examples of this are in several well known (O'Reilly) Perl books.

FishMonger
Veteran

Oct 21, 2009, 4:45 PM

Post #8 of 16 (849 views)

Re: [kev670] Binary Search Help please [In reply to]	Can't Post

I forgot, I did make 1 minor adjustment.

change:

Code

my $mid = ($low + $high)/2;

to:

Code

my $mid = int(($low + $high)/2);

kev670
Novice

Oct 21, 2009, 4:47 PM

Post #9 of 16 (848 views)

Re: [FishMonger] Binary Search Help please [In reply to]	Can't Post

In Reply To

Are you aware that you are performing numeric comparisons of strings? For example:

Code

 if  (($namesArray[$mid] lt $nameHolder))

While it is legal, I suspect it is not what you want to do.

Actually, in this case it is exactly what is needed and examples of this are in several well known (O'Reilly) Perl books.

Well they are 2 strings so i thought that this was the proper way to compare them.

Im not looking for the straight up answer but can anyone point me in the right direction. I need to place this code in a bigger program which searches an undefined array of strings and checks for a match. as i said in this tester program cill and zzz are giving back false when i input them.

kev670
Novice

Oct 21, 2009, 4:54 PM

Post #10 of 16 (845 views)

Re: [FishMonger] Binary Search Help please [In reply to]	Can't Post

In Reply To

I forgot, I did make 1 minor adjustment.

change:

Code

 my $mid = ($low + $high)/2;

to:

Code

 my $mid = int(($low + $high)/2);

It's still giving me back the same problem when i changed this i also changed the names of the items in the array. for some reason its not checking position [1] and position [4] properly

FishMonger
Veteran

Oct 21, 2009, 5:01 PM

Post #11 of 16 (842 views)

Re: [kev670] Binary Search Help please [In reply to]	Can't Post

Code

C:\test>type BinarySearch.pl 
 #!/usr/bin/perl 
use strict; 
use warnings; 
 
 
my @namesArray  = ("bill", "cill", "dill", "fill", "zzzz"); 
 
        print "\tName: "; 
 
        my $name; 
 
        $name = <STDIN>; 
 
        chomp($name); 
 
        my $i = &binarySearch ($name,@namesArray); 
 
        print "$i"; 
 
sub binarySearch 
{ 
my ($nameHolder, @namesArray) = @_; 
my $high=@namesArray-1; 
 
    my $low = 0; 
 
 
 
        while ($low <= $high) 
        { 
                print "low:$low \t high:$high\n"; 
 
                my $mid = int(($low + $high)/2); 
 
                if  (($namesArray[$mid] lt $nameHolder)) 
                { 
 
 
                        $low  = $mid + 1; 
 
                } 
 
                elsif (($namesArray[$mid] gt  $nameHolder)) 
                { 
                        #print "hi tere 2"; 
 
                        $high = $mid - 1; 
 
                } 
                else 
                { 
                        return 1; 
                } 
        } 
 
     return 0; 
 
}

Code

C:\test>BinarySearch.pl 
        Name: cill 
low:0    high:4 
low:0    high:1 
low:1    high:1 
1 
C:\test>BinarySearch.pl 
        Name: zzzz 
low:0    high:4 
low:3    high:4 
low:4    high:4 
1

kev670
Novice

Oct 21, 2009, 5:01 PM

Post #12 of 16 (841 views)

Re: [FishMonger] Binary Search Help please [In reply to]	Can't Post

In Reply To

I forgot, I did make 1 minor adjustment.

change:

Code

 my $mid = ($low + $high)/2;

to:

Code

 my $mid = int(($low + $high)/2);

Thanks a lot for your help. placing an int infront of the $mid calculation solved my problem. I'm new to perl so i dont quite understand why this fixed my problem. Anyone have any ideas. Were the values in low and high not already integers...

FishMonger
Veteran

Oct 21, 2009, 5:08 PM

Post #13 of 16 (836 views)

Re: [kev670] Binary Search Help please [In reply to]	Can't Post

Code

my $mid = ($low + $high)/2;

That creates a floating point number which is carried over to the $low and $high vars.

kev670
Novice

Oct 21, 2009, 5:10 PM

Post #14 of 16 (834 views)

Re: [FishMonger] Binary Search Help please [In reply to]	Can't Post

In Reply To

Code

my $mid = ($low + $high)/2;

That creates a floating point number which is carried over to the $low and $high vars.

Thanks FishMonger. Your patience with me is much appreciated

FishMonger
Veteran

Oct 21, 2009, 5:22 PM

Post #15 of 16 (833 views)

Re: [kev670] Binary Search Help please [In reply to]	Can't Post

Try this hash look up version.

Code

#!/usr/bin/perl 
 
use strict; 
use warnings; 
 
my %hash = map { $_, 1; } qw(bill cill dill fill zzzz); 
 
print "Name: "; 
 
chomp(my $name = <STDIN>); 
 
print exists $hash{$name} ? 1 : 0;

kev670
Novice

Oct 21, 2009, 5:29 PM

Post #16 of 16 (830 views)

Re: [FishMonger] Binary Search Help please [In reply to]	Can't Post

In Reply To

Try this hash look up version.

Code

#!/usr/bin/perl 
 
use strict; 
use warnings; 
 
my %hash = map { $_, 1; } qw(bill cill dill fill zzzz); 
 
print "Name: "; 
 
chomp(my $name = <STDIN>); 
 
print exists $hash{$name} ? 1 : 0;

Ya, Thats a hell of a lot cleaner then what i had

Search for (options)

Web Applications & Managed Hosting Powered by Gossamer Threads
Visit our Mailing List Archives