#308 · Subiectul II · Programare

Poziția unui element într-un vector ordonat — căutare binară

✓ Rezolvare explicatăTeleorman 2026 · nr. 67

Enunț

Se citește un vector cu n elemente ordonate crescător, n fiind un număr natural citit de la tastatură. Să se afișeze poziția unui element x, unde x este un număr întreg citit de la tastatură. Dacă x nu se găsește în vector, să se afișeze mesajul „Nu există".

Exemple

Date de intrare	Date de ieșire
`3` `14 91 102` `3`	`Nu exista`
`5` `1 3 3 3 9` `3`	`2`

Primul exemplu e cel oficial. Pozițiile se numără de la 1; dacă x apare de mai multe ori, se afișează prima poziție. Mesajul e scris fără diacritice, pentru consolă.

Rezolvare

C++

#include <iostream>
using namespace std;

int main() {
    int n, x, v[101];
    cin >> n;
    for (int i = 0; i < n; i++)
        cin >> v[i];
    cin >> x;

    int st = 0, dr = n - 1, poz = -1;
    while (st <= dr) {
        int mij = (st + dr) / 2;
        if (v[mij] == x) {
            poz = mij;
            dr = mij - 1;            // poate mai e unul in stanga
        }
        else if (v[mij] < x) st = mij + 1;
        else dr = mij - 1;
    }

    if (poz == -1) cout << "Nu exista";
    else cout << poz + 1;
    return 0;
}

Exersează mai departe

Probleme cu aceeași tehnică

#074ProgramareElevii ordonați descrescător după medie, folosind date structurate #283ProgramarePoziția unui element în vectorul ordonat, fără a-l ordona #314ProgramareElementul care apare de cele mai multe ori într-un vector #336ProgramareOrdonarea crescătoare după numărul de cifre, apoi după valoare #344ProgramareOrdonarea descrescătoare după ultima cifră, apoi după valoare #569ProgramareElementele comune ale unui tablou crescător și ale unuia descrescător (subprogramul tablou)