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

Binary search

Original: Căutarea binară

O(log n)C++1767 lines2 examples

The idea

It only works on an array sorted in increasing order. We compare x with the middle element of the range [st, dr]: if they are equal, we are done; if x is smaller, we search left of the middle, otherwise to the right. At every step the range is halved. A position where x is found is printed, or NO.

Original description (Romanian)

Funcționează doar pe un vector sortat crescător. Comparăm x cu elementul din mijlocul zonei [st, dr]: dacă e egal, am terminat; dacă x e mai mic, căutăm în stânga mijlocului, altfel în dreapta. La fiecare pas zona se înjumătățește. Se afișează o poziție pe care se află x sau NU.

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

Examples

Example 1

Input

8
2 5 8 12 16 23 38 56
23

Expected output

6
Example 2

Input

8
2 5 8 12 16 23 38 56
7

Expected output

NU

The code

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

cautare-binara.cpp
/*
 * Titlu: Căutarea binară
 * Clasa: 9
 * Capitol: Sortare și căutare
 * Descriere: Funcționează doar pe un vector sortat crescător. Comparăm x cu
 *            elementul din mijlocul zonei [st, dr]: dacă e egal, am terminat;
 *            dacă x e mai mic, căutăm în stânga mijlocului, altfel în dreapta.
 *            La fiecare pas zona se înjumătățește. Se afișează o poziție pe care
 *            se află x sau NU.
 * Complexitate: O(log n)
 *
 * Exemplu
 * Intrare:
 * 8
 * 2 5 8 12 16 23 38 56
 * 23
 * Ieșire: 6
 *
 * Exemplu
 * Intrare:
 * 8
 * 2 5 8 12 16 23 38 56
 * 7
 * Ieșire: NU
 */
#include <iostream>
using namespace std;

int v[100001];

int main()
{
    int n, x;
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        cin >> v[i];
    }
    cin >> x;
    int st = 1, dr = n, poz = 0;
    while (st <= dr && poz == 0)
    {
        int mij = (st + dr) / 2;
        if (v[mij] == x)
        {
            poz = mij;
        }
        else if (x < v[mij])
        {
            dr = mij - 1;
        }
        else
        {
            st = mij + 1;
        }
    }
    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.