Paghahanap nin Ternarya

An sarong algoritmong paghahanap nin ternarya  sarong teknik sa siyensya nin kompyuter para sa paghanap kan minimum o maksimum kan sarong unimodal na punsyunar (function).

 An punsyunar 

Ipamugtak na kita naghahanap nin pinakahalangkaw (maksimum) na  asin na aram ta na an pinakahalangkaw yaon sa pagtanga kan  asin . Tanganing an algoritmo magin aplikable, dapat igwa nin nagkapirang halaga na  na
 para sa gabos na  na may , igwa kita nin , asin
 para sa gabos na  na may , igwa kita nin .

 Algoritmo

Tuguti na an  magin sarong unimodal na punsyunar sa sarong interbal . Kuanon an arin man na duwang punto  asin  sa segment na ini: . Dangan igwa nin tolong posibilidad:
 kun an , dangan an kinakaipuhan na pinakahalangkaw dai pwedeng makua sa wala na lado – . An boot sabihon kaini na an pinakahalangkaw orog pang may boot na hilingon sana sa lakdang na 
 kun an , na an sitwasyon kapareho kan nakaagi, sagkod sa simetriya. Ngunyan, an kinakaipuhan na pinakahalangkaw dai pwedeng yaon sa too – , kaya magduman sa segment na 
 kun an , kun siring an paghanap dapat na gibohon sa , alagad an kasong ini pwedeng ikaatribwir sa arin man sa mga nakaaging duwa (tanganing mapasimple an kodigo). Sa dai mahahaloy an laba kan segment magigin mas hababa pa sa sarong patienot nang itinalaan na konstante, asin an proseso puwedeng mapundo.

mga puntong pagpipilian  asin :



 An pagkasunod-sunod kan oras nin pagdalagan
  (sa paagi kan Master Theorem)

 Rekursibong algoritmo 
def ternary_search(f, left, right, absolute_precision) -> float:
    """Left and right are the current bounds;
    the maximum is between them.
    """
    if abs(right - left) < absolute_precision:
        return (left + right) / 2

    left_third = (2 * left + right) / 3
    right_third = (left + 2 * right) / 3

    if f(left_third) < f(right_third):
        return ternary_search(f, left_third, right, absolute_precision)
    else:
        return ternary_search(f, left, right_third, absolute_precision)

 Iteratibong algoritmo

def ternary_search(f, left, right, absolute_precision) -> float:
    """Find maximum of unimodal function f() within [left, right].
    To find the minimum, reverse the if/else statement or reverse the comparison.
    """
    while abs(right - left) >= absolute_precision:
        left_third = left + (right - left) / 3
        right_third = right - (right - left) / 3

        if f(left_third) < f(right_third):
            left = left_third
        else:
            right = right_third

    # Left and right are the current bounds; the maximum is between them
    return (left + right) / 2

Mga toltolan