Clasa a IX-a · Sortare și căutareRead in English

Căutarea secvențială în C++

În engleză: Linear search

O(n)C++1756 de linii2 exemple

Ideea

Verificăm elementele pe rând, de la primul, până găsim valoarea x sau terminăm vectorul. Merge pe orice vector, sortat sau nu. Se afișează poziția primei apariții a lui x sau NU dacă x lipsește.

Descrierea în engleză

We check the elements one by one, starting from the first, until we find the value x or reach the end of the array. It works on any array, sorted or not. The position of the first occurrence of x is printed, or NO if x is missing.

Complexitate
O(n)
Clasa
Clasa a IX-a (Grade 9)

Exemple

Exemplul 1

Intrare

6
4 8 15 16 23 15
15

Ieșire așteptată

3
Exemplul 2

Intrare

3
1 2 3
7

Ieșire așteptată

NU

Codul C++

Codul complet, cu comentarii în română. Îl poți modifica liber și îl poți reseta oricând.

cautare-secventiala.cpp
/*
 * Titlu: Căutarea secvențială
 * Clasa: 9
 * Capitol: Sortare și căutare
 * Descriere: Verificăm elementele pe rând, de la primul, până găsim valoarea x
 *            sau terminăm vectorul. Merge pe orice vector, sortat sau nu. Se
 *            afișează poziția primei apariții a lui x sau NU dacă x lipsește.
 * Complexitate: O(n)
 *
 * Exemplu
 * Intrare:
 * 6
 * 4 8 15 16 23 15
 * 15
 * Ieșire: 3
 *
 * Exemplu
 * Intrare:
 * 3
 * 1 2 3
 * 7
 * Ieșire: NU
 */
#include <iostream>
using namespace std;

int v[1001];

int main()
{
    int n, x;
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        cin >> v[i];
    }
    cin >> x;
    int poz = 0;
    for (int i = 1; i <= n && poz == 0; i++)
    {
        if (v[i] == x)
        {
            poz = i;
        }
    }
    if (poz != 0)
    {
        cout << poz << '\n';
    }
    else
    {
        cout << "NU" << '\n';
    }
    return 0;
}

Rulează pe un g++ adevărat (C++17, -O2) prin Compiler Explorer. Programele trebuie să se termine repede: există o limită de timp.