...
Eroare Algoritmi și structuri de date · Căutare binară și sortări

bisect_left în loc de bisect_right: numărul de valori dintr-un interval iese prea mic

Pe scurt

bisect_left(lista, b) dă poziția dinaintea primei apariții a lui b, deci valorile egale cu b nu sunt numărate. Pentru câte valori sunt în intervalul [a, b] folosește bisect_right(lista, b) - bisect_left(lista, a).

Explicat de Tudor Andrei Dumitrescu, Senior Software Developer, fondatorul Academiei ProgramatorilorActualizat la

Ce înseamnă

Pe o listă sortată, bisect_left(lista, x) returnează primul index la care ai putea insera x înaintea tuturor valorilor egale cu el, iar bisect_right(lista, x) (sau bisect.bisect) returnează indexul de după ultima valoare egală. Diferența dintre ele e exact numărul de apariții ale lui x.

Pentru a număra valorile din intervalul închis [a, b], capătul din stânga trebuie să includă valorile egale cu a (deci bisect_left), iar capătul din dreapta să includă valorile egale cu b (deci bisect_right). Dacă folosești bisect_left la ambele capete, numeri de fapt [a, b) și pierzi toate valorile egale cu b.

Nu primești nicio eroare. Greșeala se vede doar când în listă există valori egale cu capetele, adică exact cazurile pe care le verifică testele.

De ce apare: cauzele frecvente

1bisect_left la capătul din dreapta

Greșit
PYTHON
return bisect_left(note, b) - bisect_left(note, a)
Corect
PYTHON
return bisect_right(note, b) - bisect_left(note, a)

bisect_right(note, b) trece de toate notele egale cu b, deci ele intră în numărătoare.

2Numărul de apariții ale unei valori

Greșit
PYTHON
aparitii = bisect_right(nums, x) - bisect_right(nums, x - 1) - 1
Corect
PYTHON
aparitii = bisect_right(nums, x) - bisect_left(nums, x)

Formula cu x - 1 merge doar pentru numere întregi și oricum are un -1 în plus. Diferența dintre dreapta și stânga pentru aceeași valoare e directă.

3Verifici existența cu bisect_right

Greșit
PYTHON
i = bisect_right(nums, x)
exista = i < len(nums) and nums[i] == x
Corect
PYTHON
i = bisect_left(nums, x)
exista = i < len(nums) and nums[i] == x

bisect_right sare peste valorile egale, deci nums[i] e deja mai mare decât x. bisect_left indică prima apariție.

Repară tu

Repară eroarea, direct în pagină

Funcția cate_note(note, a, b) numără câte note dintr-un catalog sortat sunt între a și b, inclusiv capetele. Testul cu assert pică: notele egale cu b nu sunt numărate. Repar-o ca să afișeze 5, 3 și 0.

Codul care dă eroarea
PYTHON
from bisect import bisect_left, bisect_right

def cate_note(note, a, b):
    return bisect_left(note, b) - bisect_left(note, a)

note = [4, 5, 5, 7, 7, 7, 9, 10]
for a, b, corect in [(5, 7, 5), (7, 7, 3), (1, 3, 0)]:
    rez = cate_note(note, a, b)
    assert rez == corect, f'interval gresit: {rez} in loc de {corect}'
    print(rez)
După reparație, programul afișează
5
3
0
Indiciu

La capătul din dreapta ai nevoie de poziția de după ultima notă egală cu b.

Cum o eviți pe viitor

Când folosești bisect, scrie-ți regula lângă cod: left = primul index cu valoare >= x, right = primul index cu valoare > x. Pentru intervale închise, stânga cu left, dreapta cu right. Testează mereu pe o listă cu valori repetate chiar la capetele intervalului și pe un interval care nu conține nimic.

Întrebări frecvente

bisect.bisect e același lucru cu bisect_right?

Da, bisect.bisect e un alias pentru bisect_right.

Merge pe o listă nesortată?

Nu. Toate funcțiile din bisect presupun o listă sortată crescător; pe una nesortată rezultatele sunt fără sens.

Erori înrudite

← Toate erorile Algoritmi și structuri de date

Tudor Andrei Dumitrescu
Cine a explicat eroarea

Tudor Andrei Dumitrescu

Senior Software Developer · fondatorul Academiei Programatorilor

LinkedIn
  1. 2019 Junior JavaCognizant Softvision
  2. 2021 Mid JavaCognizant Softvision
  3. 2022 Team LeaderEndava
  4. 2023 Senior Software DeveloperUniCredit
  5. Acum Senior Software DeveloperHCLTech
Certificat de absolvire Instructor / Preparator formare, Tudor Andrei Dumitrescu
Certificat de formator autorizatMinisterul Muncii și Ministerul Educației · 2022
Certificat de absolvire Instructor / Preparator formare, Tudor Andrei Dumitrescu

Certificat de formator autorizat · Ministerul Muncii și Ministerul Educației · 2022

Din 2020 construiește Academia Programatorilor, iar din 2026 și JoburiIT.ro. Fiecare eroare de aici a fost reprodusă în editorul nostru: codul greșit chiar dă mesajul din titlu, iar reparația chiar funcționează.

Învață Algoritmi și structuri de date de la zero, cu exerciții la fiecare lecție

Curs Algoritmi pentru interviuri: lecții scurte, fiecare cu un exercițiu verificat automat, direct în browser. Primele 2 lecții sunt gratuite.