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.

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 sorro 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};
int i=0;
int j=N-1;
int somma;

while (i<j) {
	somma=a[i]+a[j];
		if (somma == x) {
		   cout<<"coppia trovata, numeri in posizione: "<<i<<", "<<j<<endl;
		   break;
		}
		else if (somma < x)
			i++;
		else 
			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.

Alcuni link utili

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++


Autore dell'articolo: cristina

Avatar per Coding Creativo

Lascia un commento

Il tuo indirizzo email non sarà pubblicato. I campi obbligatori sono contrassegnati *