Grade 9 · Sorting and searchingCitește în română

Linear search

Original: Căutarea secvențială

O(n)C++1756 lines2 examples

The idea

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.

Original description (Romanian)

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.

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

Examples

Example 1

Input

6
4 8 15 16 23 15
15

Expected output

3
Example 2

Input

3
1 2 3
7

Expected output

NU

The code

Comments are in Romanian, as in the original collection. Edit freely: you can reset at any time.

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;
}

Runs on a real g++ (C++17, -O2) through Compiler Explorer. Keep runs short; there's a time limit.