Algorithmus finden, der prüft, ob gegebene Zahl Summe zweier Zahlen eines Arrays ist

Question

hat jemand eine Idee, wie ein Algorithmus aussehen könnte, der bei einem gegebenen Array aus n ganzen Zahlen und einer gegebenen Zahl c in Zeit O(n*log(n)) entscheidet, ob es zwei Zahlen a und b aus dem Array gibt, sodass a+b=c gilt?

Würde mich sehr über Tipps freuen. 

Answer 1

wenn du was flottes zum Suchen hast vielleicht so

( in pascalähnlicher Notation)

For k:=1 to n 
        begin
        x:=c-feld[k]

         suche x in feld[k+1] bis feld[n]

       end;

besser wohl wenn die äußere Schleife auch biem Finden

abbrechen kann.

 

Comments

Danke. Ich habe das so ähnlich gemacht. Erstmal das Array in O(nlog(n)) aufsteigend sortieren und danach etwa so wie du es beschrieben hast suchen.