मैं पर्ल में बाइनरी खोज कैसे कार्यान्वित कर सकता हूं?

Question

मैं पर्ल में एक बाइनरी खोज एल्गोरिदम लागू करना चाहता हूं। मेरा 'सरणी' घटते क्रम में क्रमबद्ध होता है (वास्तविक सरणी नहीं, बल्कि एक फ़ंक्शन जो इंडेक्स प्राप्त करता है और मान देता है)। समस्या यह है कि समान मूल्यों का विस्तार हो सकता है। यदि मेरा खोज मूल्य इस तरह के खिंचाव में है, तो मैं इसे शामिल करने वाली पहली अनुक्रमणिका वापस करना चाहता हूं।

यह मैं क्या लिखा है:

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

} 

और इस का उपयोग करने के लिए एक सरल उदाहरण है:

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

समस्या मुझे यकीन है कि मेरी किसी और पिछले (## SEE MY QUESTION BELOW ## के साथ चिह्नित नहीं कर रहा हूँ है) सुंदर है"। क्या ऐसा करने का कोई बेहतर तरीका है?

Answer 1

हालांकि मैं शुरुआत में एक्समन के उत्तर के साथ सहमत हूं ... यह एक छोटे से तरीके से है, जो रैखिक तर्क (कम से कम एक छोटा सा) का उपयोग करने में मेरे पहले (वास्तव में खराब) उत्तर के समान है। विशेष रूप से, पर $mid - 1 के साथ कॉल करने का कोई कारण नहीं है। यह एक अनावश्यक रैखिक खोज चरण है।

यहां मैं सुझाव दूंगा। रैखिक खोज से परहेज करने के लिए इसके अलावा, यह अत्यंत सरल होने का लाभ है:

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

हालांकि मैं पहले एफएम का जवाब, मामला है कि आप (सभी शून्यों के साथ) दिखाने के साथ सहमति व्यक्त की एक रेखीय के लिए एक अच्छा मामला नहीं है वापस खोज और हालांकि मुझे यह पसंद नहीं आया कि आपने बस बाइनरी खोज जारी रखी, "पहले x" में एक गणना योग्य मान है, और अभी भी में उप-रैखिक प्रदर्शन है, जबकि रैखिक बैक सर्च में है - पाठ्यक्रम - एक रैखिक एक।

तो मैं अपने विचार पसंद है, लेकिन यह इस तरह अधिक कॉम्पैक्ट है:

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

रैखिक वापस खोज एक आसान गणना है, लेकिन मूल्य कार्यों को और अधिक जटिल है, कम संगणना के रूप में बेहतर।

Answer 3

आप Newton's approximation method देख रहे हैं।