3 ms·
All right. It's in perl. Here's what I have: sub binary_search { my($ary, $val) = @_; print "Looking for $val...\n"; $val < $ary->[0] and
by Dove 17y ago
All right. It's in perl. Here's what I have:
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.
- RiderOfGiraffes 17y agoCan/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.
- Dove 17y agoHaving to do it in C is even more perverse than doing it in my head. ;)
- Dove 17y agoIn 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.
- joezydeco 17y agoAn array of length Maxint?
- ableal 17y agoGood call. As per link in http://news.ycombinator.com/item?id=1277701 http://news.ycombinator.com/item?id=1277701 (elsewhere in this page): 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
- ay 17y ago"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! http://stdio.be/mybsearch/mybsearch.txt http://stdio.be/mybsearch/mybsearch.txt for the text and the http://stdio.be/mybsearch/mybsearch.c http://stdio.be/mybsearch/mybsearch.c for the notangle-d C code, if you fancy to look at it.
- drtse4 17y agoSeems 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 :)