Algoritmo complessità n log n

[Neda2]

Buongiorno. Avrei da implementare un algoritmo di complessità n log n, il quale dato un intero k e un array A di interi, verifica se in A sono presenti due numeri la cui somma è uguale a k. Naturalmente n è il numero di elementi di A

[Eruannon]

Prova ad usare ricerca binaria una volta aver ordinato l'array originario usando un algoritmo di complessità nlogn (ad esempio Heapsort). Una volta ordinato, per ogni elemento dell'array verifichi con ricerca binaria, di costo log n, se in A esiste un altro elemento pari a k - l'elemento corrente, quello è l'elemento da te cercato. Se la ricerca fallisce per ognuno degli n elementi allora non esistono due elementi tali da soddisfare la tua richiesta. Il costo totale è dato dalla complessità dell'algoritmo di ordinamento più la complessità delle n chiamate a ricerca binaria, il costo è quindi n log n.

[Neda2]

io avevo pensato di fare cosi: ordinavo l'array con il merge sort che ho gia implementato, e poi controllavo gli elementi dell array ordinato partendo dagli estremi. Quindi posti i=0 e j=n-1(n dimensione di A), controllavo se la somma di A+A[j] fosse uguale a k, se non lo era allora vedevo se la somma era minore di K andavo avanti con l'indice i, altrimenti andavo indietro con l'indice j. Può essere accettabile come soluzione?

[apatriarca]

Mi sembra possa andare bene.

[Neda2]

Va bene grazie mille per l'aiuto.