Finden Sie das mittlere Element in verschmolzenen Arrays in O (logn)

Question

Wir haben zwei sortierte Arrays der gleichen Größe n. Lassen Sie uns das Array a und b aufrufen.

Wie finden Sie das mittlere Element in einem sortierten Array von a und b zusammengeführt?

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:

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

---

Zeitaufwand: O (log n). Irgendwelche Ideen?

Answer 1

Schauen Sie auf die Mitte der beiden Arrays. Nehmen wir an, ein Wert ist kleiner und der andere ist größer.

Verwerfen Sie die untere Hälfte des Arrays mit dem kleineren Wert. Verwerfen Sie die obere Hälfte des Arrays mit dem höheren Wert. Jetzt haben wir die Hälfte von dem, womit wir begonnen haben.

Spülen und wiederholen, bis nur noch ein Element in jedem Array übrig ist. Bringe den kleineren von diesen beiden zurück.

Wenn die beiden mittleren Werte gleich sind, wählen Sie beliebig.

Credits: Bill Li's blog

Answer 2

Ziemlich interessante Aufgabe. Ich bin mir nicht sicher über O (logn), aber Lösung O ((logn)^2) ist für mich offensichtlich. Wenn Sie die Position eines Elements im ersten Array kennen, dann können Sie herausfinden, wie viele Elemente in beiden Arrays kleiner sind als dieser Wert (Sie wissen bereits, wie viele kleinere Elemente im ersten Array sind und wie Sie kleinere Elemente im zweiten Array finden) binäre Suche - also summiere einfach diese zwei Zahlen). Wenn Sie also wissen, dass die Anzahl der kleineren Elemente in beiden Arrays kleiner als N ist, sollten Sie in die erste Hälfte des ersten Arrays schauen, andernfalls sollten Sie in die untere Hälfte gehen. So erhalten Sie allgemeine binäre Suche mit interner binärer Suche. Die Gesamtkomplexität ist O ((logn)^2)

Hinweis: Wenn Sie im ersten Array keinen Median finden, starten Sie die erste Suche im zweiten Array. Dies hat keinen Einfluss auf die Komplexität

Answer 3

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

Sie kenne die k-te Position im Ergebnisarray im Voraus basierend auf n, was gleich n ist. Das Ergebnis n-te Element könnte im ersten Array oder zweiten sein. Nehmen wir zuerst an, dass Element im ersten Array ist, dann binäre Suche, die mittleres Element von [l, r] nimmt, am Anfang l = 0, r = 3; Mit mittleren Element wissen Sie, wie viele Elemente im gleichen Array kleiner, das ist Mitte - 1. Wenn Sie wissen, dass das Element middle-1 weniger ist und Sie wissen, dass Sie ein n-tes Element benötigen, können Sie das [n - (middle-1)] te Element aus dem zweiten Array kleiner, größer haben. Wenn das größer ist und das vorherige Element kleiner ist als das, was Sie brauchen, wenn es größer ist und das vorherige ebenfalls größer ist, müssen wir L = Mitte, wenn es kleiner ist, r = Mitte. Tun Sie dasselbe für das zweite Array, falls Sie keine Lösung für das erste gefunden haben. Insgesamt log (n) + log (n)