I look at it more as an exercise akin to athletes running with weights. When compared with competition conditions, it is totally unrealistic, but it definitely strengthens you.

  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'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

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