Finde das mittlere Element in verschmolzenen Arrays in O (logn)

Sehen Sie sich die Mitte der beiden Arrays an. 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. Gib den kleineren von diesen beiden zurück.

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

Danksagungen: Bill Lis Blog

Sehr 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 sich im ersten Array befinden und Sie können kleinere Elemente im zweiten Array mit binär finden) 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 wird 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

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

Sie kennen die k-te Position im Ergebnisarray im Voraus basierend auf n, was gleich n ist. Das Ergebnis, das n-te Element, könnte im ersten Array oder in der zweiten sein. Nehmen wir zuerst an, dass das Element dann in der ersten Matrix ist mache die binäre Suche, die das mittlere Element von [l, r] nimmt, am Anfang l = 0, r = 3; Wenn Sie also das mittlere Element verwenden, wissen Sie, wie viele Elemente in demselben Array kleiner sind. 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 oder 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. Dann machen Sie dasselbe für das zweite Array, falls Sie keine Lösung für das erste gefunden haben. Insgesamt log (n) + log (n)