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.

Scatena il tuo potenziale con ’50 Algoritmi per imparare C++’, il libro appena lanciato su Amazon che ti guiderà nel mondo della programmazione con passione e precisione!

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.

Scatena il tuo potenziale con ’50 Algoritmi per imparare C++’, il libro appena lanciato su Amazon che ti guiderà nel mondo della programmazione con passione e precisione!

Alcuni link utili

Indice argomenti linguaggio C++

Esercizi con gli array in C++

Esercitazione sugli array in C++

Array in C++

Passaggio di parametri per valore o per riferimento

Equazioni di secondo grado in C++

Le variabili globali e loali in C++

Uso delle funzioni in C++

Funzioni in C++

Definizione di funzioni in C++

Libreria cmath

Come usare il for in C++

Massimo tra n numeri in C++

Iterazioni in C++

Ciclo while in C++

Ciclo do while

Operatori logici in C++

Esercizi con switch case in C++

If else in C++

Casting in C++

Tutorial C++

Successione di Fibonacci in C++