Intervale închise și semi-deschise: indicii în C++

Intervalul [l,r] include ambele capete. Intervalul [l,r) include începutul și exclude capătul drept. Ambele convenții sunt utile, dar formulele și condițiile buclelor trebuie să corespundă aceleiași alegeri.

Aceleași elemente, alte capete

Pozițiile 2,3,4 pot fi descrise prin [2,4] sau prin [2,5). În primul caz, lungimea este 4-2+1=3. În al doilea, lungimea este 5-2=3. Capătul drept exclus arată unde se oprește prelucrarea, nu ultimul element citit.

Pentru un tablou cu n elemente numerotate de la zero, întregul domeniu valid este [0,n). Poziția n este o margine validă a intervalului, dar nu un indice valid pentru accesarea unui element.

Intervalul gol are o reprezentare simplă

În convenția semi-deschisă, [l,l) este gol: lungimea este zero și bucla nu execută corpul. Aceasta face naturală reprezentarea unei căutări fără rezultate sau a unei secvențe cu zero elemente.

În convenția cu ambele capete incluse, trebuie să stabilești separat cum reprezinți golul, de exemplu prin l mai mare decât r. Dacă indicii sunt fără semn, expresii precum n-1 pentru n=0 cer atenție: scăderea nu produce un indice negativ obișnuit.

Pozițiile 2,3,4 sunt descrise atât de intervalul închis [2,4], cât și de intervalul semi-deschis [2,5). Lungimile sunt 4−2+1 și 5−2, ambele 3.Mărește schema ↗

Împărțirea fără suprapunere

Un interval [l,r) poate fi împărțit la m în [l,m) și [m,r). Niciun element nu este pierdut și niciunul nu este prelucrat de două ori. Această proprietate este utilă în sortări și în algoritmi care divid secvența.

Dacă folosești intervale închise, împărțirea trebuie adaptată, de exemplu [l,m] și [m+1,r]. Folosirea aceleiași margini incluse în ambele jumătăți ar dubla elementul de la mijloc și poate împiedica progresul unei recursii.

Verifică bucla după sensul intervalului

Pentru [l,r), condiția obișnuită este i mai mic decât r. Pentru [l,r], este i mai mic sau egal cu r. Nu schimba semnul condiției fără să schimbi și definiția marginii.

Testează un interval cu un singur element, unul gol și unul care ajunge exact la sfârșitul tabloului. Scrie manual indicii vizitați înainte de rulare. Dacă lista indicilor este corectă, poți verifica separat calculele efectuate pe valori.

Continuă cu parcurgerea vectorilor, căutarea binară și sumele parțiale.

Întrebări frecvente

Care este diferența dintre [l,r] și [l,r)?

Intervalul închis [l,r] include ambele capete. Intervalul semideschis [l,r) include l și exclude r. Capătul exclus indică locul opririi, nu ultimul element procesat.

Cum calculez numărul pozițiilor dintr-un interval?

Pentru indici întregi și l≤r, [l,r] are r-l+1 poziții, iar [l,r) are r-l poziții. Formula trebuie să corespundă aceleiași convenții ca bucla.

De ce este util intervalul semideschis la vectori?

Cele n elemente indexate de la zero ocupă [0,n), iar [l,l) descrie natural un interval gol. Această convenție simplifică lungimile și permite împărțirea în intervale alăturate fără suprapunere.