Grade 10 · Divide and conquerCitește în română

Recursive binary search

Original: Căutare binară recursivă

O(log n)C++1754 lines2 examples

The idea

The array is sorted in increasing order. We compare x with the middle element: if they are equal we are done; if x is smaller, we search only the left half, otherwise only the right one. Unlike the sum or the maximum with divide and conquer, here we solve a single subproblem at every step. If the portion becomes empty (st > dr), x does not appear. The position of x (numbered from 1) or 0 is printed.

Original description (Romanian)

Vectorul este sortat crescător. Comparăm x cu elementul din mijloc: dacă sunt egale am terminat; dacă x este mai mic, căutăm doar în jumătatea stângă, altfel doar în cea dreaptă. Spre deosebire de suma sau maximul prin divide et impera, aici rezolvăm o singură subproblemă la fiecare pas. Dacă porțiunea devine vidă (st > dr), x nu apare. Se afișează poziția lui x (numerotată de la 1) sau 0.

Complexity
O(log n)
Grade
Grade 10 (Clasa a X-a)

Examples

Example 1

Input

7
1 3 5 7 9 11 13
9

Expected output

5
Example 2

Input

7
1 3 5 7 9 11 13
4

Expected output

0

The code

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

cautare-binara-recursiva.cpp
/*
 * Titlu: Căutare binară recursivă
 * Clasa: 10
 * Capitol: Divide et impera
 * Descriere: Vectorul este sortat crescător. Comparăm x cu elementul din mijloc:
 *            dacă sunt egale am terminat; dacă x este mai mic, căutăm doar în
 *            jumătatea stângă, altfel doar în cea dreaptă. Spre deosebire de suma
 *            sau maximul prin divide et impera, aici rezolvăm o singură subproblemă
 *            la fiecare pas. Dacă porțiunea devine vidă (st > dr), x nu apare.
 *            Se afișează poziția lui x (numerotată de la 1) sau 0.
 * Complexitate: O(log n)
 *
 * Exemplu
 * Intrare:
 * 7
 * 1 3 5 7 9 11 13
 * 9
 * Ieșire: 5
 *
 * Exemplu
 * Intrare:
 * 7
 * 1 3 5 7 9 11 13
 * 4
 * Ieșire: 0
 */
#include <iostream>
using namespace std;

int v[100001];

int cauta(int st, int dr, int x)
{
    if (st > dr)
        return 0;
    int m = (st + dr) / 2;
    if (v[m] == x)
        return m;
    if (x < v[m])
        return cauta(st, m - 1, x);
    return cauta(m + 1, dr, x);
}

int main()
{
    int n, x;
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> v[i];
    cin >> x;
    cout << cauta(1, n, x) << '\n';
    return 0;
}

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