News for hackers. Stuff that matters.
Re:Are you one of the 10% of programmers who can write a bin... by RiderOfGiraffes on Monday April 19, 2010 @05:15PM (#1277870)
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.
Re:Are you one of the 10% of programmers who can write a bin... by Dove on Monday April 19, 2010 @05:36PM (#1277920)
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.
Re:Are you one of the 10% of programmers who can write a bin... by RiderOfGiraffes on Monday April 19, 2010 @05:43PM (#1277932)
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.

Re:Are you one of the 10% of programmers who can write a bin... by Dove on Monday April 19, 2010 @05:48PM (#1277945)
Having to do it in C is even more perverse than doing it in my head.

;)

Re:Are you one of the 10% of programmers who can write a bin... by Dove on Monday April 19, 2010 @06:56PM (#1278104)
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.
Re:Are you one of the 10% of programmers who can write a bin... by ay on Monday April 19, 2010 @11:38PM (#1278559)
"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 for the text and the http://stdio.be/mybsearch/mybsearch.c for the notangle-d C code, if you fancy to look at it.

Re:Are you one of the 10% of programmers who can write a bin... by joezydeco on Monday April 19, 2010 @09:36PM (#1278354)
An array of length Maxint?
Re:Are you one of the 10% of programmers who can write a bin... by ableal on Tuesday April 20, 2010 @06:07AM (#1279054)
Good call. As per link in 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

Re:Are you one of the 10% of programmers who can write a bin... by drtse4 on Monday April 19, 2010 @06:18PM (#1278018)
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 :)
Re:Are you one of the 10% of programmers who can write a bin... by kragen on Monday April 19, 2010 @11:31PM (#1278547)
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.