CodeUtility
Facilitiamo la vita agli sviluppatori!
Algoritmi C/C++

La ricerca binaria in C e C++

In questa lezione cercherai in un array ordinato in tempo O(log n) con un ciclo scritto a mano in C e con std::lower_bound in C++.

Introduzione

La ricerca binaria confronta il valore cercato con l'elemento centrale dell'intervallo di ricerca e scarta la metà che non può contenerlo. Ripetendo il procedimento, l'intervallo si restringe molto rapidamente, ma i dati in ingresso devono essere già ordinati.

Punti importanti

  • Prova con input vuoti, con un solo elemento, con valori ripetuti e già ordinati.
  • Prima fai funzionare il codice correttamente, poi ottimizza.
  • Nel codice reale preferisci le funzioni pronte della libreria standard.

Visualizzatore di La ricerca binaria in C e C++

O(log n)

Usa Avvia o Passo per seguire ogni confronto e spostamento dei dati.

Esempi di codice C e C++

C
Esegui →
main.c
#include <stdio.h>

int search(const int *values, int size, int target) {
    int low = 0;
    int high = size - 1;
    while (low <= high) {
        int middle = low + (high - low) / 2;
        if (values[middle] == target) return middle;
        if (values[middle] < target) low = middle + 1;
        else high = middle - 1;
    }
    return -1;
}

int main(void) {
    int values[] = {3, 7, 11, 16, 23, 28};
    printf("index=%d\n", search(values, 6, 23));
}
Risultato dell'esecuzione
index=4
C++
Esegui →
main.cpp
#include <algorithm>
#include <iostream>
#include <vector>

int main() {
    std::vector values{3, 7, 11, 16, 23, 28};
    auto match = std::lower_bound(values.begin(), values.end(), 23);
    std::cout << "index="
              << std::distance(values.begin(), match) << '\n';
}
Risultato dell'esecuzione
index=4

Confronto tra C e C++

Nella versione in C, la posizione centrale si calcola come low + (high - low) / 2 invece di (low + high) / 2, per evitare un overflow quando gli indici sono molto grandi. A ogni confronto, low o high si sposta sulla metà rimasta. La versione in C++ usa std::lower_bound per trovare la prima posizione non minore del valore cercato. Entrambe hanno complessità O(log n).

C

Cicli, puntatori, lunghezze e buffer temporanei sono scritti esplicitamente.

C++

Iteratori e algoritmi standard separano l'elaborazione dal modo in cui i dati sono memorizzati.

Esercizi di approfondimento

Esegui entrambe le versioni e poi modifica il codice per osservare la differenza di sicurezza che offre ciascun linguaggio.

  • Simula ogni confronto su carta.
  • Prova con valori ripetuti e con valori molto grandi e molto piccoli.
  • Misura il tempo del tuo codice e confrontalo con la libreria standard.

Esercitati con una sfida

Usa ciò che questa lezione spiega per risolvere un problema reale. Ogni sfida gira nel browser, con test immediati e una revisione dell'IA.

Tutte le sfide