sub binary_search {
my($ary, $val) = @_;
print "Looking for $val...\n";
$val < $ary->[0] and return undef;
$val > $ary->[-1] and return undef;
my $min = 0;
my $max = @$ary - 1;
my $mid = int(($max + $min)/2);
while($max - $min > 1) {
$ary->[$mid] == $val and return $mid;
$ary->[$mid] > $val and $max = $mid;
$ary->[$mid] < $val and $min = $mid;
$mid = int(($max + $min)/2);
}
$ary->[$min] == $val and return $min;
$ary->[$max] == $val and return $max;
return undef;
}
my $ary_size = int(rand(10));
my @ary;
for(my $i = 0; $i < $ary_size; $i++) {
push(@ary, int(rand(10));
}
@ary = sort @ary;
print join(",", @ary), "\n";
my $rv = binary_search(\@ary, int(rand(10)));
print "Returned $rv\n";
I see already that it has the famous 'large array' bug. Not something I encounter in my work, so I'm not on the lookout for it. I'm curious if you'll find anything else wront with it.
Seems ok to me, liked the "($max - $min > 1)" and "$ary->[$min] ==/$ary->[$max] ==" that removed the need to add or subtract 1 inside the while, nice to see a variation once in a while :)
Can/do you write in C? Would someone care to translate this?
I'll do it tomorrow at work, but if someone can post and/or email me an equivalent C version it will reduce my time. Not a problem, but just more convenient.
You'll need to give me some way to contact you so I can send you the results.
EDIT: I've just realised the spec I usually give asks for the first occurence of a key to be returned in the case where there are duplicate keys. I'll modify my tests to account for that. It's an especially useful feature in a binary search, but rarely implemented.
In all seriousness, if you have to translate it, don't bother. I write in C nearly daily, and I certainly wouldn't trust myself not to lose something in translation.
I'd be interested in what's in your test suite, though. I must sheepishly admit that my 'fairly exhaustive' test consisted of running the above random input until I'd seen all the usual tricky cases go by:
- an array of length zero
- an array of length one
- an array of length two
- the value is present
- the value is absent and too small
- the value is absent and too large
- the value is absent and in the middle
- the value is the first entry
- the value is the last entry
- the array is all one value
- there are multiple copies of the value you're looking for
If you've got anything more interesting in that test suite, that'd be good to know. Like I said, I represent the one-bazillionth of programmers that actually have a recurring professional interest in correctly coding binary searches.
"the array is all one value" got me. After fixing that, despite of the excessive verbosity, my experiment in literate programming passes the other tests - but I'm sure I coded a few more bugs in it - if you have some stock suite to get it through - would be very interested to know how many!
the binary search program that Bentley proved correct and subsequently tested in Chapter 5 of Programming Pearls contains a bug [...] it fails if the sum of low and high is greater than the maximum positive int
