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).
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.
** 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] $
(1) When $ f (k) \ geqq t $ $ f (k) \ geqq t \ leftrightarrow k \ geqq x ^ \ * $ ($ \ because f $ is a monotonically increasing function) Therefore, $ x ^ \ * $ is included in $ [l, k] $.
(2) When $ f (k) <t $ $ f (k) <t \ leftrightarrow k <x ^ \ * $ ($ \ because f $ is a monotonically increasing function) Therefore, $ x ^ \ * $ is included in $ (k, r] $.
Therefore, (✳︎) is shown from (1) and (2).
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.
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.
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)
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)
** 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] $.
(1) When $ x ^ \ * \ in [l, c_1] $ Since $ x ^ \ * \ leqq c_1 \ leqq c_2 $, there exists $ \ lambda \ in [0,1] $ which is $ c_1 = \ lambda x ^ \ * + (1- \ lambda) c_2 $. At this time,
\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}
(2) When $ x ^ \ * \ in [c_1, c_2] $ At least one of $ f (c_1) \ leqq f (c_2) $ and $ f (c_1) \ geqq f (c_2) $ holds.
(3) When $ x ^ \ * \ in [c_2, r] $ By doing the same as (1), $ f (c_1) \ geqq f (c_2) $ can be obtained.
Therefore, (✳︎) is shown from (1) to (3).
The figure below shows the partition of the ternary search section. I hope it helps you to understand.
Below is a concrete implementation of the ternary search (I think commenting out in the code will help in the implementation).
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))
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))
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.
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.
Recommended Posts