bisect_left e bisect_right
Trovare i punti di inserimento in una lista ordinata
bisect_left e bisect_right è una lezione Coding Interview Prep gratuita su CoddyKit. Questa è la lezione 2 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 Coding Interview Prep, e i tuoi progressi si sincronizzano tra il web e l'app CoddyKit. Il corso Coding Interview Prep include 4 lezioni in totale.
Cerchi senza codice ripetitivo
Il modulo bisect di Python offre una ricerca binaria testata per le liste ordinate. Nessun ciclo scritto a mano significa nessun bug off-by-one da correggere.
import bisectPunti di inserimento, non valori booleani
Invece di true o false, bisect restituisce un indice in cui inserire un valore per mantenere ordinata la lista. Questo indice è il vero punto di forza.
a = [1, 3, 3, 3, 7]bisect_left tende a sinistra
bisect_left restituisce la prima posizione in cui potrebbe essere inserito il valore. In presenza di duplicati, si colloca prima di tutti gli elementi uguali, mai dopo.
bisect.bisect_left(a, 3) # 1bisect_right tende a destra
bisect_right restituisce la posizione subito dopo l'ultimo elemento uguale. In presenza di duplicati, si colloca dopo ogni valore corrispondente.
bisect.bisect_right(a, 3) # 4Conti gli elementi uguali
Sottragga i due valori per contare i duplicati di un valore in O(log n). right meno left restituisce esattamente il numero di occorrenze.
lo = bisect.bisect_left(a, 3)
hi = bisect.bisect_right(a, 3)
print(hi - lo) # 3Il valore era presente?
Per verificare l'appartenenza, ricavi i da bisect_left e verifichi che a[i] sia uguale al target. Prima controlli che i non abbia raggiunto la lunghezza della lista.
i = bisect.bisect_left(a, x)
found = i < len(a) and a[i] == xPrimo elemento almeno pari a x
bisect_left individua anche il primo elemento maggiore o uguale a x. Quell'indice indica direttamente la risposta relativa al limite inferiore.
i = bisect.bisect_left(a, x) # first >= xPrimo elemento strettamente maggiore
Le serve il primo elemento strettamente maggiore di x? bisect_right restituisce direttamente quell'indice, il corrispondente limite superiore.
i = bisect.bisect_right(a, x) # first > xInserisca mantenendo l'ordinamento
insort trova la posizione e inserisce l'elemento con una sola chiamata, mantenendo ordinata la lista. È utile quando costruisce al volo una struttura ordinata.
bisect.insort(a, 5) # a stays sortedCerchi all'interno di una finestra
Gli argomenti opzionali lo e hi limitano la ricerca a una porzione. Così evita di fare copie quando le interessa solo un intervallo secondario.
bisect.bisect_left(a, x, 2, 5)Usi le chiavi tramite una lista di supporto
bisect confronta gli elementi completi; per cercare in base a un campo, crei una lista parallela contenente solo quelle chiavi e applichi bisect a quella.
keys = [p[0] for p in pairs]
i = bisect.bisect_left(keys, target)Controllo rapido
Ragioni sui duplicati e sui punti di inserimento.
Riepilogo: padronanza di bisect
Ora sa trovare punti di inserimento, contare i duplicati e individuare i limiti inferiore e superiore in tempo logaritmico. Ricorra a bisect prima di scrivere un ciclo. ✨
Domande Frequenti
La lezione «bisect_left e bisect_right» è gratuita?
Sì — il testo completo di «bisect_left e bisect_right» è 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 Coding Interview Prep, passa a CoddyKit PRO. Il corso Coding Interview Prep include 4 lezioni in totale.
Cosa imparerò in «bisect_left e bisect_right»?
Trovare i punti di inserimento in una lista ordinata Eserciti Coding Interview Prep 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 Coding Interview Prep?
Non è richiesta alcuna esperienza precedente. Coding Interview Prep su CoddyKit è strutturato per principianti e studenti avanzati, quindi puoi iniziare da qui o dall'inizio e procedere al tuo ritmo. Questa è la lezione 2 di 4.
Quanto tempo richiede la lezione «bisect_left e bisect_right»?
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 Coding Interview Prep?
Sì. Ogni lezione Coding Interview Prep 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