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.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.
;)
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.http://stdio.be/mybsearch/mybsearch.txt for the text and the http://stdio.be/mybsearch/mybsearch.c for the notangle-d C code, if you fancy to look at it.
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
-- find index of thing in sorted things in the range [first, last)
function bsearch_2(things, thing, first, last)
if first == last then return nil end
assert(last > first)
local midpoint = math.floor((first + last) / 2)
assert(midpoint >= first)
assert(midpoint < last)
local test = things[midpoint]
if test == thing then return midpoint end
if test > thing
then return bsearch_2(things, thing, first, midpoint)
else return bsearch_2(things, thing, midpoint+1, last)
end
end
function bsearch(things, thing)
return bsearch_2(things, thing, 1, #things+1)
end
That's Lua, which uses 1-based indices. I'd be happy to hook up input-output stuff to it if you like.