Wann zu verwenden

Beurteilen Sie wiederholt die Größe von N Elementen

Wenn Sie den Maximal- / Minimalwert finden, der die Bedingung erfüllt.
Beim Zählen der Elemente, die die Bedingungen erfüllen.
Wenn Sie den K-ten einer sortierten Liste finden. (Anzahl der Zahlen kleiner oder gleich der K-ten Zahl in der Liste <= Maximalwert, der K erfüllt)

Was ist gut

Wenn Sie sich jeden einzelnen ansehen, können Sie normalerweise die Stelle verkürzen, an der die Reihenfolge von O (N) auf O (log N) gesetzt wird.

Was ist zu tun

Sortieren Sie N Elemente im Voraus.
Wählen Sie zwei "äußere Werte" an beiden Enden aller sortierten Elemente aus. (= Wenn der Anfangswert auf beide Enden gesetzt ist, wird dieser Punkt nicht ausgewertet, sodass er ungültig ist, wenn alle wahr / falsch sind.)
Wiederholen Sie die folgenden Vorgänge, um schließlich die Grenze zwischen ok, das die Bedingung erfüllt, und ng, die dies nicht tut, zu finden.
Bestimmen Sie, ob der Durchschnittswert (Mittelpunkt) der beiden Werte die Bedingung erfüllt, und setzen Sie als Wert des Mittelpunkts ok, wenn er erfüllt ist. Wenn nicht erfüllt, wird ng als Mittelpunkt festgelegt.
Beenden Sie die Iteration, wenn die Differenz zwischen den absoluten Werten von ok und ng kleiner als 1 ist. (= Grenze wurde gefunden)

Bild

Denken

Welche Seite ist Richtig / Falsch, wenn die sortierte Liste gemäß den Bedingungen überprüft wird?

Vorlage

`Zustandsbeurteilung`


def is_ok(mid: int):
    #Spielen Sie zuerst Dinge, die sich nicht im Suchziel befinden(Wenn es sich um einen Listenindex handelt, liegt er außerhalb des Bereichs.)
    if mid < 0:
        return True | False     # ※1
    elif mid >= N:
        return True | False
    return True | False #Ergebnis der Urteilsbedingung

1: Geben Sie die linke Seite des endgültigen Listenstatus an.
True ----||---- False → True
False ----||---- True → False

`Suchausführungsteil`


def binSearch(ok: int, ng: int):
    #print(ok, ng)              #Erster Binärzustand
    while abs(ok - ng) > 1:     #Endbedingung (wenn die Differenz 1 ist und die Grenze gefunden wird)
        mid = (ok + ng) // 2
        if is_ok(mid):
            ok = mid            #Wenn Mitte die Bedingungen erfüllt, ist es bis Mitte in Ordnung, also bringen Sie OK in die Mitte
        else:
            ng = mid            #Wenn mid die Bedingungen nicht erfüllt, ist es ng bis mid, also bring ng in die Mitte
        #print(ok, ng)          #Binärzustand für jeden Schnitt in zwei Hälften
    return ok                   #Es ist grundsätzlich in Ordnung herauszunehmen.(Je nach Problem)

`Lauf`


#Suchbereich ist 0~Bis zu N.
INF = N + 1
binSearch(-1, INF)

Beginnen Sie bei der Ausführung an beiden Stellen an einer Stelle ± 1 (Beachten Sie, dass es keine Rolle spielt, wie viel externer Wert hier eingegeben wird).
Geben Sie beim Aufruf die Reihenfolge der Argumente ein, die ok und ng entsprechen. (offensichtlich)

Anwendungsbeispiel

1 Einfaches Muster, um den Maximalwert zu finden, der die Bedingung erfüllt

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):
        #Urteilsbedingungen
        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 Muster zum Zählen derjenigen, die die Bedingungen erfüllen

2-1 Einfaches 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 wenn es nicht PyPy ist.)

2-2 Dichotomisierte Suche nach beiden über / unter dem Schwellenwert

ABC077 C - Snuke Festival

Punkt: Bei drei Schwankungswerten kann die Anzahl der Muster durch Fixieren der Mitte unterdrückt werden.

def solve(N: int, A: "List[int]", B: "List[int]", C: "List[int]"):
    #Maximalwert+Auf 1 setzen
    INF = N + 1
    A.sort()
    B.sort()
    C.sort()
    
    # True - ok - ng - False
    def is_ok(mid: int, b: int):
        #Urteilsbedingungen
        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):
        #Urteilsbedingungen
        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 Wenn Sie den K-ten einer sortierten Liste finden. (Minimum X, bei dem die Anzahl der K-ten Zahl X oder weniger K oder mehr erfüllt)

Genauer gesagt: "Das Problem, das K-te beim Anordnen in einer Reihe zu finden. Wenn es jedoch zu groß ist, um alle Elemente aufzulisten."

ARC037 C-100 Millionen Massenberechnung

Dieses Problem kann gelöst werden, indem N ^ 2 Zahlen sortiert werden, um die K-te Zahl zu finden, aber bis zu 9 * 10 ^ 8 Teile sind TLE. Daher ändern wir die Art und Weise, wie wir das Problem wahrnehmen. Finde die K-te Nummer X. = Es gibt K Zahlen, die kleiner als diese Zahl X sind. Dichotomisierte Suche unter der Bedingung, dass die Anzahl der Produkte X oder weniger K oder mehr beträgt.

Beim Finden der 5. (K = 5) von 1,1,2,2,2,2,2,4,4.

2 bei X = 1 (<5) → Nr 7 für X = 2 (> = 5) → ok

Der fünfte ist 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):
        #Urteilsbedingungen
        if mid < 0:
            return False
        elif mid >= INF:
            return True
        count = 0
        for a in A:
            maxb = mid // a                 #Der Maximalwert von b, der kleiner oder gleich dem Wert in der Mitte ist, wenn das Produkt für jedes a genommen wird
            count += bisect_right(B, maxb)  #Wenn der Index aus dem sortierten B erhalten wird, sind alle b davor b, deren Produkt mit a n oder weniger ist, und die Zahl wird erhalten.
        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

Referenz

https://www.forcia.com/blog/001434.html

[PYTHON] Zusammenfassung der Halbierungssuche für Wettbewerbsprofis