Binary search summary for competition professionals

When to use

Repeatedly judge the size of N elements

  1. When finding the maximum / minimum value that satisfies the condition.
  2. When counting the elements that satisfy the conditions.
  3. 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

image

image.png

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

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)

Example of use

1 Simple pattern to find the maximum value that satisfies the condition

ABC146 C - Buy an Integer

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

ABC143 D - Triangles

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

ABC077 C - Snuke Festival

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

Binary search summary for competition professionals
[For competition professionals] Run-length compression summary
[For competition professionals] Summary of doubling
[For competition professionals] Minimum spanning tree summary
[For competition professionals] Union Find Tree Summary
[For competition professionals] Prime number, divisor, prime factorization summary
[For competition pros] Priority queue (heapq) Summary
visualize binary search
ABC146C (binary search)
Confirmation of basic matters of competition professional ~ Binary search ~
Binary search in Python
Binary search (python2.7) memo
[Python] Binary search ABC155D
Binary search with python
Binary search with Python3
Summary for learning RAPIDS
Binary search in Python (binary search)
Search list for duplicate elements
Search for strings in Python
Search for OpenCV function names
Search for strings in files
Binary search in Python / C ++
Algorithm in Python (binary search)
Pipenv usage summary (for myself)
Search numpy.array for consecutive True
Reference resource summary (for beginners)