Ricerca Binaria
Immagina di aver annotato le altezze di tutti gli edifici al mondo in ordine crescente. Quindi, il primo elemento corrisponde all’edificio più basso e l’ultimo a quello più alto. Giochiamo a un gioco in cui, data un’altezza che rappresenta un edificio, devi rispondere con la posizione (l’indice) di quell’edificio nella lista. Nel caso in cui non esista un edificio con l’altezza richiesta, la risposta deve essere -1.
Un approccio elementare sarebbe quello di utilizzare un ciclo
for che esamina ogni elemento nell’array e lo confronta con la query. Nel caso peggiore, ciò implicherebbe n operazioni per ogni query (dove il numero di elementi nell’array è n).h = [...] # Altezze di tutti gli edifici in ordine crescente
q = int(input()) # L'altezza richiesta
for i, height in enumerate(h):
if height == q: # Se troviamo l'elemento
print(i) # Stampa l'indice
break # E si ferma
else: # Se non abbiamo trovato un edificio con altezza q (else = no break)
print(-1) # Stampa -1 per indicare che non è stato trovatoTuttavia, dal momento che la lista è ordinata in modo crescente, possiamo notare che stiamo eseguendo un gran numero di confronti inutili. Invece di scorrere la lista dall’inizio alla fine, potremmo ignorare direttamente alcune parti per arrivare più velocemente all’indice corretto.
Dato che l’array è ordinato in modo crescente, un metodo più efficiente sarebbe considerare l’elemento centrale. Se tale elemento è minore di
q, possiamo scartare tutta la metà sinistra dell’array e concentrarci solo su quella destra. Se invece è maggiore di q, scartiamo la parte destra e restiamo con quella sinistra. Questo processo di controllare l’elemento centrale e di eliminare la metà non pertinente fino a trovare l’elemento giusto è essenzialmente l’algoritmo della Ricerca Binaria.h = [...] # Altezze di tutti gli edifici in ordine crescente
q = int(input()) # L'altezza richiesta
l, r = 0, len(h) # La risposta si troverà sempre tra [l; r). Nota che r è esclusivo
while r - l > 1: # C'è almeno un elemento nel mezzo da considerare
mid = (l + r) // 2 # Prendi l'indice centrale
if h[mid] > q: # h[mid] > q => scarta la metà destra
r = mid
else: # h[mid] <= q => scarta la metà sinistra
l = mid
# Dovremmo arrivare a h[l] come l'elemento richiesto
print(l if h[l] == q else -1)Per fare un esempio, supponiamo di avere un array di altezze
h = [20, 22, 23, 23, 34, 49, 52, 55, 58] e vogliamo sapere l’indice di un edificio con altezza 49.Con questo algoritmo, eseguiremmo diverse iterazioni:
mid = (0 + 9) // 2 = 4⇒h[4] = 34≤49⇒ scartiamo la parte sinistra.
mid = (4 + 9) // 2 = 6⇒h[6] = 52>49⇒ scartiamo la parte destra.
mid = (4 + 6) // 2 = 5⇒h[5] = 49≤49⇒ scartiamo la parte sinistra.
l = 5,r = 6⇒r - l == 1⇒ il ciclo while termina e stampiamo 5 dal momento cheh[5] = 49.
Potrebbe non sembrare un grande risparmio su un piccolo esempio, ma immagina di avere 10 miliardi di edifici. Se decidessimo di controllare ogni singolo edificio in ordine, nel peggior caso faremmo 10 miliardi di confronti. Ma se ogni volta dividiamo per due l’array per cercare il risultato, il miglioramento è enorme. Vediamo quante iterazioni servirebbero per dividere 10 miliardi di elementi a metà ogni volta:
Spoiler: sono solo 32 iterazioni invece di 10 miliardi
- 10,000,000,000 / 2 = 5,000,000,000
- 5,000,000,000 / 2 = 2,500,000,000
- 1250000000 / 2 = 625000000
- 625000000 / 2 = 312500000
- 312500000 / 2 = 156250000
- 156250000 / 2 = 78125000
- 78125000 / 2 = 39062500
- 39062500 / 2 = 19531250
- 19531250 / 2 = 9765625
- 9765625 / 2 = 4882812
- 4882812 / 2 = 2441406
- 2441406 / 2 = 1220703
- 1220703 / 2 = 610351
- 610351 / 2 = 305175
- 305175 / 2 = 152587
- 152587 / 2 = 76293
- 76293 / 2 = 38146
- 38146 / 2 = 19073
- 19073 / 2 = 9536
- 9536 / 2 = 4768
- 4768 / 2 = 2384
- 2384 / 2 = 1192
- 1192 / 2 = 596
- 596 / 2 = 298
- 298 / 2 = 149
- 149 / 2 = 74
- 74 / 2 = 37
- 37 / 2 = 18
- 18 / 2 = 9
- 9 / 2 = 4
- 4 / 2 = 2
- 2 / 2 = 1
Dunque, immagina un algoritmo che, con 10 miliardi di elementi, impiega 1 secondo per controllare ciascun elemento. Alla fine ci metterebbe 317 anni per concludere. Con la ricerca binaria, invece, tutte le operazioni si chiuderebbero in circa 32 secondi!
Questa è la differenza fra effettuare operazioni in e in .
Challenge
Dato un elenco di
n GPAs (valutazioni da 1 a 4, dove 1 è il voto più basso e 4 è il voto perfetto), e diverse soglie, devi stabilire quanti studenti passerebbero alla classe successiva sapendo che una GPA è sufficiente per passare se è uguale o superiore alla soglia.Input
La prima riga dell’input contiene un singolo intero
n (1 ≤ n ≤ ): il numero di studenti.La riga successiva contiene
n numeri in virgola mobile che rappresentano le GPAs degli studenti in ordine crescente (1 ≤ ≤ 4).La terza riga dell’input contiene un singolo intero
q (1 ≤ q ≤ ): il numero di soglie da considerare.L’ultima riga dell’input contiene
q numeri in virgola mobile che rappresentano le soglie minime per passare alla classe successiva (1 ≤ ≤ 4).Output
Il programma deve stampare
q righe. La riga i deve contenere il numero di studenti che superano la soglia .Examples
Input | Output |
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