Ricerca binaria classica senza bug
Impostare correttamente il ciclo con low, high e mid
Ricerca binaria classica senza bug è una lezione Competitive Programming Academy gratuita su CoddyKit. Questa è la lezione 1 di 4. Puoi leggere la lezione completa qui gratuitamente — poi esercitati direttamente nel browser con un editor di codice integrato e un tutor IA disponibile 24/7. Fa parte del percorso di apprendimento Competitive Programming Academy, e i tuoi progressi si sincronizzano tra il web e l'app CoddyKit. Il corso Competitive Programming Academy include 4 lezioni in totale.
Dimezzi lo spazio di ricerca
La ricerca binaria trova un valore in una lista ordinata dimezzando l'intervallo a ogni passaggio. Così trasforma una scansione lenta O(n) in una ricerca rapida O(log n).
a = [1, 3, 5, 7, 9] # must be sortedL'ordinamento è la regola fondamentale
La ricerca binaria funziona solo su dati ordinati. Se la lista non è ordinata, la ordini prima; in caso contrario il risultato sarà privo di significato e errato.
a.sort() # ascending order requiredDue confini
Inizi con due puntatori: low all'indice 0 e high all'ultimo indice. Se è presente, il target si trova sempre tra questi due estremi.
low, high = 0, len(a) - 1Trovi il punto centrale in sicurezza
Calcoli mid come low + (high - low) // 2. In Python l'overflow non è un problema, ma questa forma è una buona pratica sicura ovunque.
mid = low + (high - low) // 2Tre esiti
Confronti a[mid] con il target. Può averlo trovato, oppure il valore può essere troppo piccolo o troppo grande. Ogni caso riduce l'intervallo in modo diverso.
if a[mid] == target:
return midTroppo piccolo, vada a destra
Se a[mid] è minore del target, la risposta deve trovarsi a destra. Sposti low su mid + 1 ed elimini la metà sinistra.
elif a[mid] < target:
low = mid + 1Troppo grande, vada a sinistra
Se a[mid] è maggiore del target, cerchi nella metà sinistra. Sposti high su mid - 1 così non controllerà mai più mid.
else:
high = mid - 1La condizione del ciclo
Continui finché low è minore o uguale a high. Quando si incrociano, l'intervallo è vuoto e il target non è presente.
while low <= high:
mid = low + (high - low) // 2Segnali l'assenza
Se il ciclo termina senza trovare una corrispondenza, il valore è assente. Per convenzione, restituisca -1, così chi chiama la funzione può distinguere il successo dal fallimento.
return -1 # target not in listLa trappola dell'off-by-one
Il bug classico consiste nel dimenticare il +1 o -1 quando si sposta un puntatore. Se lo omette, mid viene verificato di nuovo all'infinito e il ciclo non termina.
low = mid + 1 # not low = midUsi la libreria quando possibile
Per una semplice verifica di appartenenza, il modulo bisect di Python offre già una ricerca priva di bug. Scriva il ciclo manualmente solo quando le serve una logica personalizzata.
import bisect
i = bisect.bisect_left(a, target)Controllo rapido
Rifletta su ciò che mantiene corretto il ciclo.
Riepilogo: ricerca senza bug
Ora sa impostare low e high, calcolare mid in modo sicuro, restringere il lato corretto ed evitare la trappola dell'off-by-one. La ricerca logaritmica è nelle sue mani. 🎯
Domande Frequenti
La lezione «Ricerca binaria classica senza bug» è gratuita?
Sì — il testo completo di «Ricerca binaria classica senza bug» è gratuito qui sul web. Per esercitarvi in modo interattivo (un editor di codice integrato e un tutor IA 24/7) e sbloccare il resto del corso Competitive Programming Academy, passa a CoddyKit PRO. Il corso Competitive Programming Academy include 4 lezioni in totale.
Cosa imparerò in «Ricerca binaria classica senza bug»?
Impostare correttamente il ciclo con low, high e mid Eserciti Competitive Programming Academy con codice pratico che esegui direttamente nel browser, e un tutor IA 24/7 risponde alle tue domande mentre lavori sulla lezione.
Ho bisogno di esperienza per iniziare Competitive Programming Academy?
Non è richiesta alcuna esperienza precedente. Competitive Programming Academy su CoddyKit è strutturato per principianti e studenti avanzati, quindi puoi iniziare da qui o dall'inizio e procedere al tuo ritmo. Questa è la lezione 1 di 4.
Quanto tempo richiede la lezione «Ricerca binaria classica senza bug»?
La maggior parte delle lezioni CoddyKit richiede circa 5–10 minuti. Ogni lezione è breve e interattiva, quindi fai progressi costanti e riprendi esattamente da dove hai lasciato su web e app.
Posso scrivere ed eseguire codice in questa lezione Competitive Programming Academy?
Sì. Ogni lezione Competitive Programming Academy include un editor di codice integrato, quindi scrivi ed esegui codice reale direttamente nel tuo browser e ricevi feedback istantaneo dall'IA — nessuna configurazione locale necessaria.
Tutte le lezioni di questo corso
- Ricerca binaria classica senza bug
- bisect_left e bisect_right
- Primo True: ricerca binaria sul predicato
- Ricerca binaria sulla risposta