Suche nach dem mittleren Element in zusammengeführten Arrays in O(logn)

Question

Wir haben zwei sortierte Arrays der gleichen Größe n. Nennen wir die Arrays a und b.

Wie findet man das mittlere Element in einem sortierten Array, das durch a und b verbunden ist?

Example:

n = 4
a = [1, 2, 3, 4]
b = [3, 4, 5, 6]

merged = [1, 2, 3, 3, 4, 4, 5, 6]
mid_element = merged[(0 + merged.length - 1) / 2] = merged[3] = 3

Kompliziertere Fälle:

Fall 1:

a = [1, 2, 3, 4]
b = [3, 4, 5, 6]

Fall 2:

a = [1, 2, 3, 4, 8]
b = [3, 4, 5, 6, 7]

Fall 3:

a = [1, 2, 3, 4, 8]
b = [0, 4, 5, 6, 7]

Fall 4:

a = [1, 3, 5, 7]
b = [2, 4, 6, 8]

---

Erforderliche Zeit: O(log n). Irgendwelche Ideen?

Answer 1

Sehen Sie sich die Mitte der beiden Felder an. Nehmen wir an, ein Wert ist kleiner und der andere größer.

Die untere Hälfte des Feldes mit dem kleineren Wert wird verworfen. Verwerfen Sie die obere Hälfte des Feldes mit dem höheren Wert. Jetzt haben wir nur noch die Hälfte von dem, womit wir angefangen haben.

Spülen und wiederholen, bis nur noch ein Element in jedem Array übrig ist. Geben Sie das kleinere dieser beiden Elemente zurück.

Wenn die beiden mittleren Werte gleich sind, dann wähle beliebig.

Credits: Bill Li's Blog

Answer 2

Eine sehr interessante Aufgabe. Ich bin mir nicht sicher über O(logn), aber die Lösung O((logn)^2) ist für mich offensichtlich. Wenn man die Position eines Elements im ersten Array kennt, dann kann man herausfinden, wie viele Elemente in beiden Arrays kleiner sind als dieser Wert (man weiß bereits, wie viele kleinere Elemente im ersten Array sind, und man kann die Anzahl der kleineren Elemente im zweiten Array mit Hilfe der binären Suche herausfinden - also einfach diese beiden Zahlen addieren). Wenn Sie also wissen, dass die Anzahl der kleineren Elemente in beiden Feldern kleiner als N ist, sollten Sie in der oberen Hälfte des ersten Feldes suchen, ansonsten in der unteren Hälfte. Sie erhalten also eine allgemeine binäre Suche mit interner binärer Suche. Die Gesamtkomplexität wird O((logn)^2) sein.

Hinweis: Wenn Sie den Median im ersten Feld nicht finden, beginnen Sie die Suche im zweiten Feld. Dies hat keine Auswirkungen auf die Komplexität

Answer 3

Wenn also n = 4 und a = [1, 2, 3, 4] und b = [3, 4, 5, 6]

Sie kennen die k-te Position im Ergebnisfeld im Voraus auf der Grundlage von n, was gleich n ist. Das n-te Element des Ergebnisses könnte sich im ersten oder zweiten Array befinden. Nehmen wir zunächst an, dass sich das Element im ersten Array befindet und Binärsuche mit mittlerem Element aus [l,r], am Anfang l = 0, r = 3; Wenn man also das mittlere Element nimmt, weiß man, wie viele Elemente im gleichen Feld kleiner sind, nämlich Mitte - 1. Wenn man weiß, dass das mittlere - 1 Element kleiner ist und man das n-te Element braucht, kann das [n - (mittlere - 1)]-te Element des zweiten Arrays kleiner oder größer sein. Wenn das größer ist und das vorherige Element kleiner ist, ist es das, was du brauchst, wenn es größer ist und das vorherige Element auch größer ist, brauchen wir L = Mitte, wenn es kleiner ist, r = Mitte. Machen Sie dasselbe für das zweite Array, falls Sie keine Lösung für das erste gefunden haben. Insgesamt log(n) + log(n)