CGI/Perl Guide | Learning Center | Forums | Advertise | Login
Site Search: in

  Main Index MAIN
INDEX
Search Posts SEARCH
POSTS
Who's Online WHO'S
ONLINE
Log in LOG
IN

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

 



kev670
Novice

Oct 21, 2009, 2:08 PM

Post #1 of 16 (1692 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 (1684 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 / Moderator

Oct 21, 2009, 4:09 PM

Post #3 of 16 (1681 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 (1678 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 / Moderator

Oct 21, 2009, 4:28 PM

Post #5 of 16 (1675 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 (1672 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 / Moderator

Oct 21, 2009, 4:39 PM

Post #7 of 16 (1668 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 / Moderator

Oct 21, 2009, 4:45 PM

Post #8 of 16 (1662 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 (1661 views)
Re: [FishMonger] Binary Search Help please [In reply to] Can't Post


In Reply To

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 (1658 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 / Moderator

Oct 21, 2009, 5:01 PM

Post #11 of 16 (1655 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 (1654 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 / Moderator

Oct 21, 2009, 5:08 PM

Post #13 of 16 (1649 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 (1647 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 / Moderator

Oct 21, 2009, 5:22 PM

Post #15 of 16 (1646 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 (1643 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) Powered by Gossamer Forum v.1.2.0

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