[PYTHON] Mathematical explanation of binary search and ternary search and implementation method without bugs

Content of this article

This article describes ** explanation of binary search and ternary search and its implementation **.

As a feature of this article, I try to explain ** mathematically rigorously **, so if you want to read an intuitive explanation, [Reference article](https://qiita.com/DaikiSuyama/items/84df26daad11cf7da453#% Please see E6% 9C% 80% E5% BE% 8C% E3% 81% AB).

Preface

In the following, the domain ** x ** of the function considered in the dichotomy (or trisection search) is set to ** the closed interval ** on the set of integers or real numbers, but in reality it is a total order set (set of rational numbers). If it is a closed interval on (including etc.), it can be a domain.

Also, on a personal computer, even a continuous set such as a real number is treated discretely, so it should be noted that the following sets are all ** discrete sets **.

In addition, I wrote the article with the utmost care, but there may be mistakes in the description. In that case, I will correct it if you can comment or edit request.

Binary search

What is binary search?

** x ** (original number is $ n $) [monotonically increasing (or decreasing) function](https://ja.wikipedia.org/wiki/%E5%8D%98%E8%AA%BF% E5% 86% 99% E5% 83% 8F) When $ f $ is defined, there exists $ x ^ \ * \ in $ ** x ** where $ f (x ^ \ *) = t $ It is an algorithm that searches $ O (\ log n) $ to find out what to do. [^ 1]

** In the following, $ f $ is implicitly used as a monotonic increasing function, but the same argument can be made even if $ f $ is a monotonically decreasing function if the inequality sign is reversed. I will. ** **

In the binary search, the minimum value is searched at high speed by searching the search area where the function $ f $ is defined by $ \ frac {1} {2} $, but under the following assumption (✳︎). Since $ \ frac {1} {2} $ is going on, (✳︎) is shown.

(✳︎) For $ x ^ \ * \ in [l, r] $ where $ f (x ^ \ *) = t $ in the closed interval $ [l, r] $, bisect $ [l, r] $ When the point is $ k $ $ f (k) \ geqq t \ rightarrow x ^ \ * \ in [l, k] $ and $ f (k) <t \ rightarrow x ^ \ * \ in (k, r] $

Reference diagram

The following is a diagram showing the behavior of binary search. I hope it helps you to understand.

---

Also, if $ false $ is $ 0 $ and $ true $ is $ 1 $, the return value is a bool value and $ x ^ \ * \ in $ ** x ** is the boundary between $ false $ and $ true $. You can think of a function like this, and you can find the boundary $ x ^ \ * $ with a similar algorithm.

Implementation of binary search

Below is a concrete implementation of binary search (I think commenting out in the code will help in the implementation).

Also, since the purpose is to confirm the implementation, I will not explain the problem I dealt with in this article, but it is recommended to solve the problem once to deepen the understanding of binary search.

(1) When the return value of the function is not a bool value

It is often used to find the $ k $ element in a sorted array. If you think of the domain ** x ** as a set of indexes and the return value of the function as an element of the array corresponding to each index, you can certainly define a monotonous function $ f $ in the domain ** x **. I understand this. Also, if you want to find $ k $ in a sorted array, you can use the bisect module so you don't have to implement a binary search yourself. For more information, see this article.

Here, we will search for the index of the element whose array $ a = [0,1,1,2,4,5,6,8,8,9,10] $ is 2 by binary search.

basicbisect.py

a=[0,1,1,2,4,5,6,8,8,9,10]

#Binary search code

#(1)l,r is l at both ends<=r
#Make sure the index l is less than 2 and r is greater than or equal to 2.
l,r=0,10
#(2)l=r or l=r-Break at 1
while l+1<r:
    #(3)Midpoint of the closed section(Truncate the fractional part of)
    #Considering the overflow, it will be written as follows
    k=l+(r-l)//2
    #(4)Partition of closed section
    #a[k]>=In the case of 2, the larger endpoint is k and a[k]<In case of 2, set the smaller end point to k
    if a[k]>=2:
        r=k
    else:
        l=k
#(5)output
#r is a[x]>=Minimum of 2 indexes(a[x]=Note that there is not always an index x that is 2.)
print(r)

(2) When the return value of the function is a bool value

If you implement binary search yourself, this pattern is most likely. In the following, the code is written based on ABC063D-Widespread, and x that makes the return value of the function $ f $ $ true $. I'm looking for the smallest of them. Also, if you want to know how to solve this problem, Main solution or My commentary article See items / 9efaf76418ef4677f979).

widespread.py

import math
n,a,b=map(int,input().split())
h=[int(input()) for i in range(n)]

def f(x):
    global n
    c=0
    for i in range(n):
        if h[i]-x*b>0:
            c+=math.ceil((h[i]-x*b)/(a-b))
    return c<=x

#Binary search code

#(1)l,r is l at both ends<=r
#At this time, confirm that l is false and r is true.
l,r=0,10**9
#(2)l=r or l=r-Break at 1
while l+1<r:
    #(3)Midpoint of the closed section(Truncate the fractional part of)
    #Considering the overflow, it will be written as follows
    k=l+(r-l)//2
    #(4)Partition of closed section
    #x=If k is true, set the larger endpoint to k and x=If k is false, set the smaller endpoint to k
    if f(k):
        r=k
    else:
        l=k
#(5)output
#r is f(x)=The smallest of true x
print(r)

Ternary search

What is a ternary search?

** x ** (original number is $ n $) ** Pseudo [convex (or concave) function](https://ja.wikipedia.org/wiki/%E5%87%B8%E9%96% A2% E6% 95% B0) ** When $ f $ is defined, $ x ^ \ * \ in $ ** x ** where $ f (x) $ is the minimum (or maximum) is $ O (\ log n) An algorithm that searches with $. Also, ** x ** always has a minimum point (or maximum point) because it is a finite set.

** In the following, $ f $ is implicitly regarded as a pseudo-convex function, but the same argument can be made even if $ f $ is a pseudo-concave function if the inequality sign is reversed. Masu **

Here, the pseudo-convex function is defined as follows. [^ 2]

$ \ Lambda x_1 + (1- \ lambda) x_2 \ in $ ** x ** for $ ^ ∀ x_1, x_2 \ in $ ** x **, $ ^ ∀ \ lambda \ in [0,1] $ Then, $ f (\ lambda x_1 + (1- \ lambda) x_2) \ leqq \ lambda f (x_1) + (1- \ lambda) f (x_2) $ holds.

In the ternary search, the minimum value is searched at high speed by searching the search area where the function $ f $ is defined by $ \ frac {2} {3} $, but under the following assumption (✳︎). This is shown because $ \ frac {2} {3} $ is added to.

(✳︎) For the minimum point $ x ^ \ * \ in [l, r] $ in the closed interval $ [l, r] $, the trisection point of that interval is $ c_1, c_2 (l \ leqq c_1 \ leqq c_2 \ leqq When r) $ $ f (c_1) \ leqq f (c_2) \ rightarrow $ The minimum point $ x ^ \ * $ is included in $ [l, c_2] $. $ f (c_1) \ geqq f (c_2) \ rightarrow $ The minimum point $ x ^ \ * $ is included in $ [c_1, r] $.

\begin{align}
f(c_1) &= f(\lambda x^*+(1-\lambda)c_2) \\
& \leqq \lambda f(x^*)+(1-\lambda)f(c_2) \ (\because f is a pseudo-convex function)\\
& \leqq \lambda f(c_2)+(1-\lambda)f(c_2) \ (\because f(x^*) \leqq f(c_2))\\
& = f(c_2)
\end{align}

Reference diagram

The figure below shows the partition of the ternary search section. I hope it helps you to understand.

---

Implementation of ternary search

Below is a concrete implementation of the ternary search (I think commenting out in the code will help in the implementation).

(1) When the domain of the function is a closed interval on a real number

In the following, consider ARC054-B Moore's Law. In this problem, the real number $ x \ in [0,10 ^ {18] that minimizes $ f (x) = x + \ frac {p} {2 ^ {\ frac {x} {1.5}}} $ }] It can be reduced to the problem of thinking about $.

Here, since this function $ f (x) $ can be differentiated twice, it is calculated as $ f ^ {''} (x) = (\ log 2) ^ 2 (-\ frac {2} {3}). ^ 2p \ times 2 ^ {-\ frac {2x} {3}}> 0 $, so you can see that the ** function $ f (x) $ is a convex function **. [^ 3]

Therefore, you can search for the minimum point $ x $ in the ternary search, and you can write the following code. Also, here, the domain of the function is not an integer but a real number, and the margin of error is allowed up to $ 10 ^ {-8} $, so the search range is $ \ frac {2} {3} $ in one search. Considering that, $ \ log_ {\ frac {3} {2}} \ frac {10 ^ {18}} {10 ^ {-8}} = 26 \ times \ log_ {\ frac {3} {2}} {10} The while statement will be rotated about $ times, which makes the program sufficiently fast.

mooreslaw.py

p=float(input())

#(1)Define the function f that you want to minimize
def f(x):
    global p
    return x+p*pow(2,-(x/1.5))

#(2)I want to find the minimum value of the function f l at both ends of the closed interval,Put with r(l<=r)
l,r=0,10**18
#(3)The error is 10^-Turn the while statement until it falls below 8.
while l+pow(10,-8)<r:
    #(4)Place trisection points as shown below to prevent overflow
    c1=l+(r-l)/3
    c2=r-(r-l)/3
    #(5)Make an update
    if f(c1)<f(c2):
        r=c2
    else:
        l=c1
#(6)The final output is l,Either r is fine
print(f(l))

(2) When the domain of the function is a closed interval on an integer

In the following, consider ABC102D-Equal Cut. Since it is a slightly different method from this solution, I will introduce My commentary article as a reference article.

Since it is a fairly difficult problem, I would like you to check only the implementation method in comparison with the case of ①.

equalcut.py

n=int(input())
a=list(map(int,input().split()))
s=[a[0]]
for i in range(1,n):
    s.append(s[-1]+a[i])

#(1)Define the function f that you want to minimize
def f(c,i):
    global n,a,s
    return abs(s[c]-(s[i]-s[c]))

#(1)
def g(c,i):
    global n,a,s
    return abs((s[c]-s[i])-(s[n-1]-s[c]))

ans=[]
for i in range(1,n-2):
    ans_=[]

    #(2)I want to find the minimum value of the function f l at both ends of the closed interval,Put with r(l<=r)
    #Here is the index value
    l,r=0,i
    #(3)Since it is an integer, r=l,l+1,l+Should be one of 2
    #On the contrary, r>=l+In case of 3, the difference between r and l can be made smaller.
    while l+2<r:
        #(4)Trisection point(Fractional part is truncated)
        c1=l+(r-l)//3
        c2=r-(r-l)//3
        #(5)Make an update
        if f(c1,i)<f(c2,i):
            r=c2
        else:
            l=c1
    #(6)The final request is l~The element of r that minimizes the value of the function f
    x=sorted([(f(j,i),j) for j in range(l,r+1)])[0][1]
    ans_.append(s[x])
    ans_.append(s[i]-s[x])

    #Decide on the right

    #(2)
    l,r=i+1,n-1
    #(3)
    while l+2<r:
        #(4)
        c1=l+(r-l)//3
        c2=r-(r-l)//3
        #(5)
        if g(c1,i)>g(c2,i):
            l=c1
        else:
            r=c2
    #(6)
    x=sorted([(g(j,i),j) for j in range(l,r+1)])[0][1]
    ans_.append(s[x]-s[i])
    ans_.append(s[n-1]-s[x])

    ans.append(max(ans_)-min(ans_))
print(min(ans))

Finally

I was disappointed that I couldn't solve the problem using the ternary search, so I considered it mathematically rigorously.

Also, please refer to the mounting part as I devised it myself.

And I would like to express my gratitude to the university synchronization for helping me make the corrections in this mathematically rigorous explanation.

Reference article

Generalization of binary search algorithm-Recommendation of binary search method- Implementation pattern of binary search that never bugs and 5 reasons why it does not bug

[^ 1]: The binary search description assumes that $ x ^ \ * $ exists, but be aware that ** $ x ^ \ * $ may not exist **. [^ 2]: We introduced a pseudo-convex function instead of a convex function because the former is defined on a continuity set and we are considering a function on a ** discrete set **. [^ 3]: For the function $ f (x) $ that can be differentiated twice on the continuity set, it is a convex function if the double differentiation is non-negative, and if it is a convex function on the continuity set, it is a subset. It is implicitly used to be a pseudo-convex function on a discrete set.