4 ms·

Do you want to send me your code for testing in my test suite? You've obviously tested it now, but it would still be interesting.

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 ago
  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.
  - Dove 17y ago
    Having to do it in C is even more perverse than doing it in my head. ;)
    - Dove 17y ago
      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.
      - joezydeco 17y ago
        An array of length Maxint?
        ableal 17y ago
        Good 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 ago
  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 :)
kragen 17y ago
Mine is: -- 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.

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 ago
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.
- Dove 17y ago
  Having to do it in C is even more perverse than doing it in my head. ;)
  - Dove 17y ago
    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.
    - joezydeco 17y ago
      An array of length Maxint?
      - ableal 17y ago
        Good 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 ago
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 :)

kragen 17y ago

Mine is: -- 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.