Wie kann ich binäre Suche in Perl implementieren?

Question

Ich möchte einen binären Suchalgorithmus in Perl implementieren. Mein 'Array' ist in absteigender Reihenfolge sortiert (nicht ein tatsächliches Array, sondern eine Funktion, die einen Index erhält und Werte zurückgibt). das Problem ist, dass es Teile von identischen Werten geben könnte. Wenn mein gesuchter Wert in einem solchen Bereich liegt, möchte ich den ersten Index zurückgeben, der ihn enthält.

Dies ist, was ich geschrieben habe:

# get_val should be a *decreasing* function for idexes $i in min..max, 
# formally: for any $i,$j s.t. $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; 

} 

und dies ist ein einfaches Beispiel für Verwendung:

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); 

Das Problem ist, ich bin mein letzten sonst nicht sicher (markiert mit ## SEE MY QUESTION BELOW ##) ist hübsch". Gibt es einen besseren Weg, das zu tun?

Answer 1

Obwohl ich anfänglich mit Axemans Antwort einverstanden war ... ist es in gewisser Weise ähnlich wie meine erste (wirklich schlechte) Antwort in der Verwendung linearer Logik (zumindest ein kleines bisschen davon). Insbesondere gibt es keinen Grund, $get_val_subref mit $mid - 1 anzurufen. Das ist ein unnötiger linearer Suchschritt.

Hier ist, was ich vorschlagen würde. Neben lineare Suche zu vermeiden, hat es den Vorteil, extrem einfach zu sein:

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

Obwohl ich zum ersten Mal mit FM Antwort, der Fall, dass Sie zeigen (mit allen Nullen) vereinbart ist kein gutes Beispiel für ein linearen Suche zurück. Und obwohl Ich mag nicht, dass man einfach die binäre Suche fort, „die erste x“ hat haben einen berechenbaren Wert, und würde noch haben sublinear Leistung, während die lineare Rück Suche hat - von natürlich - ein linear eins.

So mag ich Ihre Idee, aber es ist kompakter wie folgt aus:

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

Die lineare zurück Suche ist ein einfacher Berechnung, aber da die Wertfunktionen erhalten komplexer, desto weniger Berechnungen desto besser.

Answer 3

Sie können nach Newton's approximation method suchen.