Ricerca in un array ordinato

Proponiamo un problema di ricerca in un array ordinato.

Prendere in input un array di N numeri interi, ordinato in modo crescente.
Viene fornito in input un numero intero X. Dire se nell'array è presente una coppia di numeri tali che sommati diano come risultato il numero X.

Dato che l'array è ordinato posso procedere in questo modo:

Prendo due indici i e j. Faccio in modo che il primo indice parta da 1 e il secondo invece dall'ultimo elemento.

Fondamenti solidi di programmazione

Impara le basi della programmazione in C in modo semplice, pratico ed efficace. Variabili, cicli, funzioni, logica e algoritmi.

9 ore di corso registrato
Più di 50 algoritmi risolti passo passo
Livello base
100% online, fruibile quando vuoi

Sommo quindi i due elementi puntati dai due indici e dopo controllo se la somma è uguale ad un numero X preso in input.

Se vero ho già trovato la coppia di numeri, altrimenti, se la somma è inferiore scorro l'indice i, in quanto ho bisogno di un numero maggiore. Mentre se la somma è superiore scorro l'indice j, in quanto ho bisogno di un numero inferiore.

Allego il listato completo della ricerca in un array ordinato in cui ho già inizializzato l'array con 5 elementi.

#include <iostream>
using namespace std;

#define x 15
#define N 5

int main() {
    int a[N] = {1, 3, 5, 10, 11}; // Dichiarazione e inizializzazione dell'array
    int i = 0; // Inizializzazione dell'indice di partenza
    int j = N - 1; // Inizializzazione dell'indice finale
    int somma; // Variabile per memorizzare la somma di due elementi

    // Ciclo per trovare la coppia di numeri che somma x
    while (i < j) {
        somma = a[i] + a[j]; // Calcolo della somma di due elementi

        if (somma == x) { // Se la somma è uguale a x, la coppia è stata trovata
            cout << "Coppia trovata, numeri in posizione: " << i << ", " << j << endl;
            break; // Esci dal ciclo
        } else if (somma < x) { // Se la somma è minore di x, aumenta l'indice i
            i++;
        } else { // Se la somma è maggiore di x, diminuisci l'indice j
            j--;
        }
    }

    return 0;
}

Chiaramente potete anche inserire voi N numeri nell'array e poi effettuare la ricerca degli elementi la cui somma deve essere uguale a X.

Questo è solo un esempio di come effettuare la ricerca in un array ordinato, proponete pure le vostre soluzioni così da discuterne assieme.

Lezione precedente: ricerca sequenziale in C++

Lezione successiva: ricerca binaria o dicotomica in C++