Binary search summary for competition professionals
When to use
Repeatedly judge the size of N elements
- When finding the maximum / minimum value that satisfies the condition.
- When counting the elements that satisfy the conditions.
- When finding the Kth of a sorted list. (Number of numbers below the Kth number in the list <= maximum value that satisfies K)
What is good
Normally, if you look at each one, you can shorten the place where the order of O (N) is taken to O (log N).
What to do
- Sort N elements in advance.
- Select two
outer valuesfrom both ends of all sorted elements. (= If the initial value is set to both ends, that point will not be evaluated, so it will be invalid if all are True / False) - Repeat the following operations to finally find the boundary between ok that satisfies the condition and ng that does not.
- Determine whether the average value (midpoint) of the two values satisfies the condition, and if it is satisfied, set ok as the value of the midpoint. If not satisfied, ng is set as the midpoint.
- End the iteration when the difference between the absolute values of ok and ng is less than 1. (= Boundary was found)
image
Thinking
Which side is True / False when the sorted list is screened according to the conditions.
template
Condition judgment
def is_ok(mid: int):
#Play things that are not in the search target first(If it's a list index, it's out of range.)
if mid < 0:
return True | False # ※1
elif mid >= N:
return True | False
return True | False #Result of judgment condition
- 1: Specify the left side of the final list status.
True ----||---- False→TrueFalse ----||---- True→False
Search execution part
def binSearch(ok: int, ng: int):
#print(ok, ng) #First binary state
while abs(ok - ng) > 1: #End condition (when the difference is 1 and the boundary is found)
mid = (ok + ng) // 2
if is_ok(mid):
ok = mid #If mid meets the conditions, it is ok up to mid, so bring ok to the middle
else:
ng = mid #If mid does not meet the conditions, ng is up to mid, so bring ng to the middle
#print(ok, ng) #Binary state for each cut in half
return ok #It is basically ok to take out.(Depending on the problem)
Run
#Search range is 0~Up to N.
INF = N + 1
binSearch(-1, INF)
- When executing, start from the place ± 1 from both ends (Note that it does not matter how much outside value is entered here)
- When calling, enter in the order of the arguments corresponding to ok and ng. (obviously)
Example of use
1 Simple pattern to find the maximum value that satisfies the condition
INF = 10 ** 9 + 1
def main():
A, B, X = map(int, input().split())
# True - ng - ok - False
def is_ok(mid: int):
#Judgment conditions
if mid < 0:
return True
elif mid >= INF:
return False
return A * mid + B * len(str(mid)) <= X
def binSearch(ok: int, ng: int):
#print(ok, ng)
while abs(ok - ng) > 1:
mid = (ok + ng) // 2
if is_ok(mid):
ok = mid
else:
ng = mid
#print(ok, ng)
return ok
print(binSearch(0, INF))
return
2 Pattern to count those that meet the conditions
2-1 Simple problem
def main():
N = int(input())
L = [int(i) for i in input().split()]
L.sort()
# True ---- False
def is_ok_top(mid: int, a: int, b: int):
if mid < 0:
return True
elif mid >= N:
return False
return L[mid] < L[a] + L[b]
def binSearch_top(ok: int, ng: int, a: int, b: int):
while abs(ok - ng) > 1:
mid = (ok + ng) // 2
if is_ok_top(mid, a, b):
ok = mid
else:
ng = mid
return ok
count = 0
for a in range(0, len(L) - 2):
for b in range(a + 1, len(L) - 1):
count += binSearch_top(-1, INF, a, b) - b
print(count)
(TLE if it is not PyPy.)
2-2 Binary search for both above / below the threshold
- Point: When there are three fluctuation values, the number of patterns can be suppressed by fixing the center.
def solve(N: int, A: "List[int]", B: "List[int]", C: "List[int]"):
#Maximum value+Set to 1
INF = N + 1
A.sort()
B.sort()
C.sort()
# True - ok - ng - False
def is_ok(mid: int, b: int):
#Judgment conditions
if mid < 0:
return True
elif mid >= N:
return False
return A[mid] < b
# False - ng - ok - True
def is_ok2(mid: int, b: int):
#Judgment conditions
if mid < 0:
return False
elif mid >= N:
return True
return C[mid] > b
def binSearch(ok: int, ng: int, b: int):
#print(ok, ng)
while abs(ok - ng) > 1:
mid = (ok + ng) // 2
if is_ok(mid, b):
ok = mid
else:
ng = mid
#print(ok, ng)
return ok
def binSearch2(ok: int, ng: int, b: int):
#print(ok, ng)
while abs(ok - ng) > 1:
mid = (ok + ng) // 2
if is_ok2(mid, b):
ok = mid
else:
ng = mid
#print(ok, ng)
return ok
sum = 0
for b in B:
a = binSearch(-1, INF, b) - 0 + 1
c = N - 1 - binSearch2(INF, -1, b) + 1
sum += a * c
#print(b, "->", a, c)
print(sum)
return
3 When finding the Kth of a sorted list. (Minimum X in which the number less than or equal to the Kth number X satisfies K or more)
More precisely, "The problem of finding the Kth when arranging in a row. However, when it is too large to enumerate all the elements."
ARC037 C -100 million mass calculation
This problem can be solved by sorting N ^ 2 numbers to find the Kth, but up to 9 * 10 ^ 8 TLE. Therefore, we change the way we perceive the problem. Find the Kth number X. = There are K numbers less than that number X. Binary search on condition that the number of products X or less is K or more.
When finding the 5th (K = 5) of 1,1,2,2,2,2,2,4,4.
2 at X = 1 (<5) → No 7 at X = 2 (> = 5) → ok
The fifth is found to be 2.
INF = 10 ** 18 + 1
def main():
N, K = map(int, input().split())
A = sorted([int(i) for i in input().split()])
B = sorted([int(i) for i in input().split()])
# False - ng - ok - True
def is_ok(mid: int):
#Judgment conditions
if mid < 0:
return False
elif mid >= INF:
return True
count = 0
for a in A:
maxb = mid // a #The maximum value of b that is less than or equal to the value mid when the product is taken for each a
count += bisect_right(B, maxb) #If the index is obtained from the sorted B, the product of all b before that is n or less, and the number is obtained.
return count >= K
def binSearch(ok: int, ng: int):
#print(ok, ng)
while abs(ok - ng) > 1:
mid = (ok + ng) // 2
if is_ok(mid):
ok = mid
else:
ng = mid
#print(ok, ng)
return ok
print(binSearch(INF, 0))
return
reference
https://www.forcia.com/blog/001434.html
Recommended Posts