How can I implement binary search in Perl? -

i implement binary search algorithm in perl. 'array' sorted in decreasing order (not actual array, function gets index , returns values). problem there might stretches of identical values. if searched value in such stretch, want return first index contains it.

this have written:

# get_val should *decreasing* function idexes $i in min..max, # formally: $i,$j s.t. $max>=$i>$j>=$min : # $get_val_subref($i, $extra) <= $get_val_subref($j, $extra) # min , max inclusive boundaries search # get_val sub should index in min..max , data reference, , return # value given index # returns smallest index $i in min..max $get_val_subref($j, $extra) # returns $searched_val, or undef if no such index exists sub binary_search {     ( $min, $max, $searched_val, $get_val_subref, $get_val_sub_extra_data )         = @_;     ( $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 question below ##              # surely $val == $searched_val, first one?              if (    $mid > $min                 , $get_val_subref->( $mid - 1, $get_val_sub_extra_data )                 == $searched_val )             {                  # $val == $searched_val , prev($val) == $searched_val                 # have continue                 $max = $mid - 1;             }             else {                  # $val == $searched_val , prev($val) != $searched_val                 # wer'e done                 return $mid;             }         }     }      # $val not found. return undef     return undef;  } 

and simple example using it:

sub get_val_sub {     ( $pos, $a ) = @_;     $val = $a->[$pos];     return $val; }  @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);  "ret:", binary_search( 0, $#arr, 0, \&get_val_sub, \@arr ); 

the problem i'm not sure last else (marked ## see question below ##) "pretty". there better way of doing that?

although agreed axeman's answer ... is, in small way, similar first (really bad) answer in using linear logic (at least small bit of it). specifically, there no reason call $get_val_subref $mid - 1. that's unnecessary linear search step.

here's suggest. in addition avoiding linear searching, has benefit of being extremely simple:

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