How to implement binary search in Perl?

Question

I would like to implement a binary search algorithm in Perl. My "array" is sorted in descending order (not the actual array, but a function that takes an index and returns values). the problem is that there can be stretches of the same values. If my search value is in such a stretch, I want to return the first index that contains it.

Here is what I wrote:

# get_val should be a *decreasing* function for idexes $i in min..max, # formally: for any $i,$j st $max>=$i>$j>=$min : # $get_val_subref($i, $extra) <= $get_val_subref($j, $extra) # min and max are the inclusive boundaries for the search # get_val sub should get an index in min..max and an extra data reference, and return # the value for the given index # returns the smallest index $i in min..max for which $get_val_subref($j, $extra) # returns $searched_val, or undef if no such index exists sub binary_search { my ( $min, $max, $searched_val, $get_val_subref, $get_val_sub_extra_data ) = @_; my ( $mid, $val ); while ( $min <= $max ) { $mid = $min + int( ( $max - $min ) / 2 ); $val = $get_val_subref->( $mid, $get_val_sub_extra_data ); if ( $val > $searched_val ) { $min = $mid + 1; } elsif ( $val < $searched_val ) { $max = $mid - 1; } else { ## SEE MY QUESTION BELOW ## # surely $val == $searched_val, but is it the first one? if ( $mid > $min and $get_val_subref->( $mid - 1, $get_val_sub_extra_data ) == $searched_val ) { # $val == $searched_val and prev($val) == $searched_val # we have to continue $max = $mid - 1; } else { # $val == $searched_val and prev($val) != $searched_val # wer'e done return $mid; } } } # $val was not found. return undef return undef; } 

and this is a simple example of its use:

 sub get_val_sub { my ( $pos, $a ) = @_; my $val = $a->[$pos]; return $val; } my @arr = (80, 40, 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0); say "RET:", binary_search( 0, $#arr, 0, \&get_val_sub, \@arr ); 

The problem is that I'm not sure that my last file (marked ## SEE MY QUESTION BELOW ## ) is "pretty." Is there a better way to do this?

Answer 1

Although I initially agreed with Axeman's answer ... it is, to a small degree, similar to my first (very poor) answer to using linear logic (at least a little of it). In particular, there is no reason to call $get_val_subref with $mid - 1 . This is an extra step in the linear search.

Here is what I would suggest. In addition to avoiding linear searches, it has the advantage of being extremely simple:

 sub binary_search { ... my ( $mid, $val, $solution ); while ( $min <= $max ) { ... else { $solution = $mid; # Store a possible solution. $max = $mid - 1; # But continue with the binary search # until $min and $max converge on each other. } } return $solution; } 

Answer 2

Although I initially agreed with the FM answer, the case you are showing (with all zeros) is not a good example for a linear backward search. And although I didn’t like the fact that you just continued the binary search, the “first x” has a computable value and will have sublinear performance, while the linear backward search is of course linear,

I like your idea, but it is more compact:

 else { return $mid unless ( $mid > $min and $get_val_subref->( $mid - 1, $get_val_sub_extra_data ) == $searched_val ); $max = $mid - 1; } 

A linear inverse search is a simpler calculation, but as value functions become more complex, the fewer the calculations, the better.

Answer 3

You may be looking for a Newton approximation method .