title: How can I implement binary search in Perl?
body: <p>I would like to implement a binary search algorithm in Perl. My 'array' is sorted in decreasing order (not an actual array, but a function that gets an index and returns values). the problem is that there might be stretches of identical values. If my searched value is in such a stretch, I want to return the first index that contains it.</p>
  
  <p>This is what I have written:</p>
  
  <pre><code># get_val should be a *decreasing* function for idexes $i in min..max,
  # formally: for any $i,$j s.t. $max&gt;=$i&gt;$j&gt;=$min :
  # $get_val_subref($i, $extra) &lt;= $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 &lt;= $max ) {
          $mid = $min + int( ( $max - $min ) / 2 );
          $val = $get_val_subref-&gt;( $mid, $get_val_sub_extra_data );
  
          if ( $val &gt; $searched_val ) {
              $min = $mid + 1;
          }
          elsif ( $val &lt; $searched_val ) {
              $max = $mid - 1;
          }
          else { ## SEE MY QUESTION BELOW ##
  
              # surely $val == $searched_val, but is it the first one?
  
              if (    $mid &gt; $min
                  and $get_val_subref-&gt;( $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;
  
  }
  </code></pre>
  
  <p>and this is a simple example for using it:</p>
  
  <pre><code>sub get_val_sub {
      my ( $pos, $a ) = @_;
      my $val = $a-&gt;[$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, \&amp;get_val_sub, \@arr );
  </code></pre>
  
  <p>The problem is I'm not sure my last else (marked with <code>## SEE MY QUESTION BELOW ##</code>) is "pretty". Is there a better way of doing that?</p>