三元検索

三値探索アルゴリズム^[1]は、単峰関数の最小値または最大値を見つけるためのコンピュータサイエンスの手法です。

の最大値を求めており、最大値がと の間 のどこかにあることがわかっていると仮定します。アルゴリズムを適用するには、${\displaystyle f(x)}$${\displaystyle A}$${\displaystyle B}$${\displaystyle x}$

• となるすべての場合、 となり、${\displaystyle a,b}$${\displaystyle A\leq a<b\leq x}$${\displaystyle f(a)<f(b)}$
• となるすべてのものについて、 が成り立ちます。${\displaystyle a,b}$${\displaystyle x\leq a<b\leq B}$${\displaystyle f(a)>f(b)}$

をある区間 上の 単峰性関数とします。この線分 内の任意の 2 点とを取ります。この場合、次の 3 つの可能性があります。 ${\displaystyle f(x)}$${\displaystyle [l;r]}$${\displaystyle m_{1}}$${\displaystyle m_{2}}$${\displaystyle l<m_{1}m_{2}$

• の場合、必要な最大値は左側 – には配置できません。つまり、最大値は区間内でのみ探すのが合理的です。${\displaystyle f(m_{1})<f(m_{2})}$${\displaystyle [l;m_{1}]}$${\displaystyle [m_{1};r]}$
• ならば、対称性までは前と同様である。ここで、必要な最大値は右側にはない –なので、セグメントに進む。${\displaystyle f(m_{1})>f(m_{2})}$${\displaystyle [m_{2};r]}$${\displaystyle [l;m_{2}]}$
• の場合、検索は で実行する必要がありますが、このケースは前の 2 つのうちのいずれかに帰属することができます (コードを簡略化するため)。遅かれ早かれ、セグメントの長さは所定の定数よりも少し短くなり、プロセスを停止できます。${\displaystyle f(m_{1})=f(m_{2})}$${\displaystyle [m_{1};m_{2}]}$

選択ポイントと： ${\displaystyle m_{1}}$${\displaystyle m_{2}}$

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

実行時間順

${\displaystyle T(n)=T(2n/3)+O(1)=\Theta (\log n)}$（マスター定理による）

def  ternary_search ( f ,  left ,  right ,  absolute_precision )  ->  float : 
"""left と right が現在の境界です。    最大値はそれらの間にあります。    """ if abs ( right - left ) < absolute_precision : return ( left + right ) / 2    


         
             

    左から3番目 =  ( 2 *左 + 右)  /  3
    右から3番目 =  (左 +  2 *右)  /  3

     f ( left_third )  <  f ( right_third )
        の場合: ternary_search ( f , left_third , right , absolute_precision )を返します。 それ以外の場合: ternary_search ( f , left , right_third , absolute_precision )を返します。   
    
            

def  ternary_search ( f ,  left ,  right ,  absolute_precision )  ->  float : 
"""[left, right] 内で単峰関数 f() の最大値を見つけます。    最小値を見つけるには、if/else ステートメントを逆にするか、比較を逆にします。    """ while abs ( right - left ) >= absolute_precision : left_third = left + ( right - left ) / 3 right_third = right - ( right - left ) / 3    


         
                
                

         f ( left_third )  <  f ( right_third )
            の場合: left  =  left_third 
        、そうでない場合: 
            right  =  right_third

     # 左と右が現在の境界です。最大値はそれらの間にあります。
     return  ( left  +  right )  /  2

• 最適化におけるニュートン法（導関数がゼロになる場所を探すのに使えます）
• 黄金分割探索（三項探索に似ており、反復ごとに f の評価にほとんどの時間がかかる場合に便利です）
• バイナリ検索アルゴリズム（導関数の符号が変化する場所を検索するために使用できます）
• 補間検索
• 指数探索
• 線形探索