Algorithmen und Datenstrukturen

Binäre Suche

Video preview
Stellen wir uns vor, wir hätten die Höhen aller Gebäude auf der Welt in aufsteigender Reihenfolge notiert. Das heißt, das erste Element ist das niedrigste Gebäude der Welt und das letzte Element ist das höchste. Wir spielen ein Spiel, bei dem uns eine Zahl gegeben wird, die eine Gebäudehöhe repräsentiert, und wir müssen als Antwort den Index dieses Gebäudes in der Liste nennen. Falls es kein Gebäude mit der gesuchten Höhe gibt, antworten wir mit -1.
Ein naiver Ansatz wäre, eine einfache for-Schleife zu nutzen und jedes Element nacheinander zu prüfen. Im schlimmsten Fall würde das für jede Anfrage n Wiederholungen erfordern (wenn n die Anzahl der Elemente im Array ist).
h = [...]                # Heights of all the buildings in increasing order
q = int(input())         # The query height

for i, height in enumerate(h):
    if height == q:      # In case we find the element
        print(i)         # Print the index
		    break            # And stop
else:                    # In case we didn't find a building with height q (else = nobreak)
    print(-1)            # Print -1 to indicate that we didn't find it
Da das Array allerdings sortiert ist, fällt auf, dass wir viele überflüssige Schritte machen. Anstatt die Liste von vorne bis hinten zu durchsuchen, könnten wir einige Sprünge machen und so schneller zum richtigen Index gelangen.
Weil das Array in aufsteigender Reihenfolge sortiert ist, lässt sich das Problem viel effektiver lösen, indem wir jeweils das mittlere Element ansehen. Ist dieses Element kleiner als q, können wir die gesamte linke Hälfte verwerfen und uns nur auf die rechte konzentrieren. Ist es größer als q, verwerfen wir die rechte Hälfte und konzentrieren uns auf die linke. So betrachten wir immer wieder das mittlere Element und werfen die überflüssige Hälfte weg, bis wir das gesuchte Element finden. Genau dies ist der Kern des Binäre Suche (Binary Search)-Algorithmus.
h = [...]                # Heights of all the buildings in increasing order
q = int(input())         # The query height

l, r = 0, len(h)         # The answer always lies between [l; r). Note that r is exclusive
while r - l > 1:         # There is at least one element in between to consider
    mid = (l + r) // 2   # Take the middle index
    if h[mid] > q:       # h[mid] > q => throw away the right half
        r = mid
    else:                # h[mid] <= q => throw away the left half
        l = mid

# We should arrive at h[l] being the query element
print(l if h[l] == q else -1)
Nehmen wir etwa an, wir hätten ein Array von Gebäudehöhen h = [20, 22, 23, 23, 34, 49, 52, 55, 58] und möchten den Index eines Gebäudes mit der Höhe 49 herausfinden.
Mit diesem Algorithmus würden wir ein paar Iterationen durchlaufen:
  1. mid = (0 + 9) // 2 = 4 ⇒ h[4] = 34 ≤ 49 ⇒ Wir verwerfen die linke Hälfte.
  1. mid = (4 + 9) // 2 = 6 ⇒ h[6] = 52 > 49 ⇒ Wir verwerfen die rechte Hälfte.
  1. mid = (4 + 6) // 2 = 5 ⇒ h[5] = 49 ≤ 49 ⇒ Wir verwerfen die linke Hälfte.
  1. l = 5, r = 6 ⇒ r - l == 1 ⇒ Die while-Schleife endet und wir geben 5 aus, da h[5] = 49 ist.
 
Dieses kleine Beispiel mag nicht wie ein großer Unterschied wirken, aber denken Sie an den Fall, in dem wir 10 Milliarden Gebäude haben. Würden wir linear über alle Elemente iterieren, bräuchten wir im schlimmsten Fall 10 Milliarden Durchläufe. Durch das fortlaufende Halbieren des Arrays und das Wegwerfen von Redundanzen ergibt sich jedoch ein massiver Performancegewinn. Schauen wir uns an, wie viele Iterationen nötig sind, um bei 10 Milliarden Elementen immer in der Mitte zu teilen:
Spoiler: es sind nur 32 Iterationen statt 10 Milliarden
  1. 10,000,000,000 / 2 = 5,000,000,000
  1. 5,000,000,000 / 2 = 2,500,000,000
  1. 1250000000 / 2 = 625000000
  1. 625000000 / 2 = 312500000
  1. 312500000 / 2 = 156250000
  1. 156250000 / 2 = 78125000
  1. 78125000 / 2 = 39062500
  1. 39062500 / 2 = 19531250
  1. 19531250 / 2 = 9765625
  1. 9765625 / 2 = 4882812
  1. 4882812 / 2 = 2441406
  1. 2441406 / 2 = 1220703
  1. 1220703 / 2 = 610351
  1. 610351 / 2 = 305175
  1. 305175 / 2 = 152587
  1. 152587 / 2 = 76293
  1. 76293 / 2 = 38146
  1. 38146 / 2 = 19073
  1. 19073 / 2 = 9536
  1. 9536 / 2 = 4768
  1. 4768 / 2 = 2384
  1. 2384 / 2 = 1192
  1. 1192 / 2 = 596
  1. 596 / 2 = 298
  1. 298 / 2 = 149
  1. 149 / 2 = 74
  1. 74 / 2 = 37
  1. 37 / 2 = 18
  1. 18 / 2 = 9
  1. 9 / 2 = 4
  1. 4 / 2 = 2
  1. 2 / 2 = 1
Stellen Sie sich also einen Algorithmus vor, der bei 10 Milliarden Elementen jedes einzelne prüft und für jede Überprüfung 1 Sekunde benötigt. Dann würde dieser Algorithmus 317 Jahre brauchen. Eine Binäre Suche würde hingegen nur 32 Sekunden dauern!
Das ist der Unterschied zwischen und Operationen.

Herausforderung

Gegeben seien n GPAs im Bereich von 1 bis 4 (wobei 1 die niedrigste Note und 4 die beste ist), sowie einige Schwellwerte. Für jeden dieser Schwellwerte soll bestimmt werden, wie viele Personen ihn erreichen oder übertreffen und somit in die nächste Klassenstufe aufsteigen können.

Eingabe

Die erste Zeile der Eingabe enthält eine einzelne ganze Zahl n (1 ≤ n ≤ ), die die Anzahl der Studierenden angibt.
Die nächste Zeile enthält n Gleitkommazahlen, die die GPAs der Studierenden in aufsteigender Reihenfolge darstellen (1 ≤ ≤ 4).
Die dritte Zeile enthält eine einzelne ganze Zahl q (1 ≤ q ≤ ), die angibt, wie viele Schwellwerte berücksichtigt werden sollen.
Die letzte Zeile der Eingabe enthält q Gleitkommazahlen, die die minimalen Schwellwerte zum Bestehen angeben (1 ≤ ≤ 4).

Ausgabe

Das Programm soll q Zeilen ausgeben. Zeile i enthält die Anzahl der Studierenden, die den entsprechenden Schwellwert erreichen oder überschreiten.

Beispiele

Eingabe
Ausgabe
10 1.1 1.2 1.4 1.7 2 3 3.3 3.5 3.8 3.8 5 3.7 3.8 1 1.5 2
2 2 10 7 6
 

Constraints

Time limit: 6 seconds

Memory limit: 512 MB

Output limit: 1 MB

To check your solution you need to sign in
Sign in to continue