Scrie pe caiet - De reținut

Titlul lecției

Ora 5: Căutarea binară - aplicații

Definiția lecției

Într-un tablou sortat, toate valorile egale cu x sunt alăturate, formând un bloc continuu; de aceea putem găsi prima și ultima apariție tot cu căutare binară. Prima apariție se obține căutând prima poziție cu a[poz] >= x: când găsim un element egal, reținem poziția și continuăm spre stânga, mutând dr = mij - 1. Ultima apariție se obține simetric, căutând ultima poziție cu a[poz] <= x și continuând spre dreapta cu st = mij + 1. După ieșirea din buclă verificăm dacă pe poziția reținută chiar se află x, altfel afișăm -1. Dacă poz este prima poziție cu valoarea >= x, atunci numărul de elemente strict mai mici decât x este poz - 1, cu poz inițializat cu n + 1 pentru cazul în care toate elementele sunt mai mici. Numărul de apariții se calculează cu formula ultima - prima + 1.

Definiții esențiale

• Într-un tablou sortat, valorile egale formează un bloc continuu de poziții alăturate.
• Prima apariție: prima poziție cu a[poz] >= x; când găsim un element egal, continuăm spre stânga (dr = mij - 1).
• Ultima apariție: ultima poziție cu a[poz] <= x; când găsim un element egal, continuăm spre dreapta (st = mij + 1).
• Numărul de elemente mai mici decât x: poz - 1, unde poz este prima poziție cu a[poz] >= x (inițializat cu n + 1).

Algoritmul cheie - pseudocod

Algoritmul cheie - cod C++

st = 1;
dr = n;
poz = 0;
while (st <= dr) {
    mij = (st + dr) / 2;
    if (a[mij] >= x) {
        poz = mij;
        dr = mij - 1;
    } else {
        st = mij + 1;
    }
}
if (poz != 0 && a[poz] == x)
    cout << poz;
else
    cout << -1;

Greșeli comune de evitare

• Oprirea căutării la primul element egal: la prima apariție trebuie să continuăm spre stânga.
• Inițializarea lui poz cu 0 la numărarea elementelor mai mici: dacă toate elementele sunt mai mici, răspunsul devine greșit; folosește n + 1.
• Verificarea lipsă a[poz] == x: fără ea putem afișa o poziție pe care nu se află valoarea căutată.

Exemplu practic

Într-un catalog de note ordonate crescător, profesorul vrea să afle câți elevi au luat exact nota x la test. Valorile egale sunt alăturate, deci numărul lor este ultima - prima + 1. Programul de mai jos găsește prima și ultima apariție a notei x, apoi afișează numărul de apariții.

#include <iostream>
using namespace std;

int main() {
    int n, a[100005], x, i, st, dr, mij, prima = 0, ultima = 0;
    cin >> n;
    for (i = 1; i <= n; i++)
        cin >> a[i];
    cin >> x;

    st = 1; dr = n;
    while (st <= dr) {
        mij = (st + dr) / 2;
        if (a[mij] >= x) {
            prima = mij;
            dr = mij - 1;
        } else {
            st = mij + 1;
        }
    }

    st = 1; dr = n;
    while (st <= dr) {
        mij = (st + dr) / 2;
        if (a[mij] <= x) {
            ultima = mij;
            st = mij + 1;
        } else {
            dr = mij - 1;
        }
    }

    if (prima != 0 && a[prima] == x)
        cout << ultima - prima + 1;
    else
        cout << 0;
    return 0;
}

Pentru notele 4 5 5 5 7 9 și x = 5, programul afișează 3 - exact numărul de elevi care au luat nota 5.

Sfaturi practice și trucuri

• Numărul de apariții: ultima - prima + 1 - două căutări binare, răspuns instant.
• Pentru „elemente <= x", caută prima poziție cu valoarea > x și scade 1.
• Testează întotdeauna cazul în care x nu apare deloc în tablou.