---

Geschrieben von ubik am 17.05.2016 um 16:55:

  Suchalgorithmus Summe zweier Zahlen gleich x

Hallo,

ich soll ein Array durchlaufen und dabei Paare finden, dessen Summe gleich x ist.

Z. B.

Im Array

1,2,3,4,5,6

mit x = 5

finden sich
2,3 und 1,4.

Habt ihr eine Idee wie ich dies in O(n) Zeit umsetzen kann?

---

Geschrieben von eulerscheZahl am 17.05.2016 um 17:01:

 

Du hast 2 Indizes. Der eine zeigt auf das erste Element (1) und der andere auf das letzte(6).
Die Summe von 1 und 6 ist größer als x=5, also musst du kleiner werden. Das heißt, du schiebst den zweiten Index nach links.
Das wiederholst du, bis die Indizes sich in der Mitte treffen.

Voraussetzung ist natürlich, dass das Array sortiert ist.