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 $f(x)$ asin na aram ta na an pinakahalangkaw yaon sa pagtanga kan $A$ asin $B$. Tanganing an algoritmo magin aplikable, dapat igwa nin nagkapirang halaga na $x$ na

• para sa gabos na $a,b$ na may $A\leq a<b\leq x$, igwa kita nin $f(a)<f(b)$, asin
• para sa gabos na $a,b$ na may $x\leq a<b\leq B$, igwa kita nin $f(a)>f(b)$.

Algoritmo

Tuguti na an $f(x)$ magin sarong unimodal na punsyunar sa sarong interbal $[l;r]$. Kuanon an arin man na duwang punto $m_{1}$ asin $m_{2}$ sa segment na ini: $l<m_{1}<m_{2}<r$. Dangan igwa nin tolong posibilidad:

• kun an $f(m_{1})<f(m_{2})$, dangan an kinakaipuhan na pinakahalangkaw dai pwedeng makua sa wala na lado – $[l;m_{1}]$. An boot sabihon kaini na an pinakahalangkaw orog pang may boot na hilingon sana sa lakdang na $[m_{1};r]$
• kun an $f(m_{1})>f(m_{2})$, na an sitwasyon kapareho kan nakaagi, sagkod sa simetriya. Ngunyan, an kinakaipuhan na pinakahalangkaw dai pwedeng yaon sa too – $[m_{2};r]$, kaya magduman sa segment na $[l;m_{2}]$
• kun an $f(m_{1})=f(m_{2})$, kun siring an paghanap dapat na gibohon sa $[m_{1};m_{2}]$, 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 $m_{1}$ asin $m_{2}$:

• $m_{1}=l+(r-l)/3$
• $m_{2}=r-(r-l)/3$

An pagkasunod-sunod kan oras nin pagdalagan

$T(n)=T(2n/3)+O(1)=\Theta (\log n)$ (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