[python][binary search]Python3による二分探索、三分探索の方法

Table of Contents

二分探索

binary search、バイナリーサーチとも。ソートされた配列で計算量が\(O(n)\)から\(O(\log_{2}{n})\)に減少させることができる。簡単なイメージとしては配列のmedianをチェックし、それが条件に当てはまるならそれより上を、当てはまらないならそれより下を\(\cdots\)という操作をくり返して、対象を半減させていくというもの。

Python code

以下は条件を満たすもののうち最大のものを探すアルゴリズム。

left = 1
right = 10**9
while left + 1 < right:
    mid = left + (right - left)//2
    if :#条件が満たされる(f(mid) == True)
        left = mid
    else :#条件が満たされない(f(mid) == False)
        right = mid

#leftは真となるxのうち最大の値
#rightは偽となるxのうち最小の値
print(left)

逆に、条件を満たすもののうち最小のものを探すアルゴリズムは以下の様になる。

left = 1
right = 10**9
while left + 1 < right:
    mid = left + (right - left)//2
    if :#条件が満たされる(f(mid) == True)
        right = mid
    else :#条件が満たされない(f(mid) == False)
        left = mid

#rightは真となるxのうち最小の値
#leftは偽となるxのうち最大の値
print(right)

三分探索

似たようなアルゴリズムに、三分探索がある。これは、たかだか一つしか極値のない関数に対して、その極値を探索するアルゴリズムである。まず、極値を求めたい関数\(f(x)\)を定義する。以下のコードでは最小値の探索を行う。

def f(x):
    global p
    return #ここに関数の定義式を記載

しかるに、二分探索と同様にleft, rightの定義を行うのであるが、もう一つ誤差の範囲の設定も必要になる。

left = 0
right = pow(10, 18) #最大値は最小値を探索する閉区間の右端とする。
limit = pow(10, -8) #誤差の範囲の設定

後は、誤差が設定された範囲を下回るまでwhileを回せば良い。

while left + limit < right:
    c1 = left + (right-left)/3
    c2 = right - (right-left)/3
    #更新を行う
    if f(c1) < f(c2):
        right = c2
    else:
        left = c1

三分探索の場合、最終的に出力するのはleft, rightのどちらでも良い。

print(f(left))

もちろん不等号の向きを逆にすることで、極大値でも極小値でも探索することができる。コードをまとめたものは以下。

#最小にする関数f(x)を定義する。

def f(x):
    global p
    return #ここに関数の定義式を記載する


left = 0
right = pow(10, 18)#最大値は最小値を探索する閉区間の右端とする。
limit = pow(10, -8)#誤差の範囲を設定。

#誤差が設定された値を下回るまでwhileを回す
while left + limit < right:
    c1 = left + (right-left)/3
    c2 = right - (right-left)/3
    #更新を行う
    if f(c1) < f(c2):
        right = c2
    else:
        left = c1

#最終的に出力するのはleft, rightのどちらでも良い
print(f(left))

黄金比探索

発展で黄金比探索というものもある。やっていることは三分探索とあまり変わらないので、コードのみ掲載する。

#発展で、黄金比分割検索も。
import math
theta = (1+math.sqrt(5))/2

left = 0
right = pow(10, 18)
limit = pow(10, -8)

#誤差が設定された値を下回るまでwhileを回す。
leftvalue = f((left*theta + right)/(theta + 1))
rightvalue = f((left + theta*right)/(theta + 1))

#更新を行う
while left + limit < right:
    if leftvalue < rightvalue:
        right = (left + theta*right)/(1+theta)
        rightvalue = leftvalue
        leftvalue = f((left*theta + right)/(1+theta))
    else:
        left = (left*theta + right)/(1 + theta)
        leftvalue = rightvalue
        rightvalue = f((left + right*theta)/(1+theta))

print(f(left))