Znajdź środkowy element w scalonych tablicach w O (logn)

Question

Mamy dwie posortowane tablice o tym samym rozmiarze n. Nazwijmy tablicę aib.

Jak znaleźć środkowy element w posortowanej tablicy połączonej przez a i b?

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 

Bardziej skomplikowane przypadki:

Przypadek 1:

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

Przypadek 2:

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

Przypadek 3:

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

Przypadek 4: wymagana

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

---

Czas: O (log n). Jakieś pomysły?

Answer 1

Spójrz na środek obu tablic. Powiedzmy, że jedna wartość jest mniejsza, a druga większa.

Odrzuć dolną połowę tablicy o mniejszej wartości. Odrzuć górną połowę tablicy o wyższej wartości. Teraz pozostaje nam połowa tego, od czego zaczęliśmy.

Płukać i powtarzać tak długo, aż w każdej z nich pozostanie tylko jeden element. Zwróć mniejszą z tych dwóch.

Jeśli dwie środkowe wartości są takie same, wybierz dowolnie.

Credits: Bill Li's blog

Answer 2

Dość ciekawe zadanie. Nie jestem pewien co do O (logn), ale rozwiązanie O ((logn)^2) jest dla mnie oczywiste. Jeśli znasz pozycję jakiegoś elementu w pierwszej tablicy, to możesz dowiedzieć się ile elementów jest mniejszych w obu tablicach, to ta wartość (wiesz już ile mniejszych elementów znajduje się w pierwszej tablicy i możesz znaleźćliczbę mniejszych elementów w drugiej tablicy używając wyszukiwanie binarne - więc zsumuj te dwie liczby). Więc jeśli wiesz, że liczba mniejszych elementów w obu tablicach jest mniejsza niż N, powinieneś zajrzeć do górnej połowy w pierwszej tablicy, w przeciwnym razie powinieneś przejść do niższej połowy. Otrzymasz ogólne wyszukiwanie binarne z wewnętrzną wyszukiwarką binarną. Ogólna złożoność będzie wynosić O ((logn)^2)

Uwaga: jeśli nie znajdziesz mediany w pierwszej tablicy, rozpocznij wyszukiwanie początkowe w drugiej tablicy. Nie będzie to miało wpływu na złożoność.

Answer 3

więc o n = 4 a = [1, 2, 3, 4], oraz b = [3, 4, 5, 6]

Ty znać k-tą pozycję w tablicy wyników z wyprzedzeniem na podstawie n, która jest równa n. Wynik n-tego elementu może znajdować się w pierwszej tablicy lub w drugiej. Załóżmy najpierw, że element znajduje się w pierwszej tablicy, a następnie przeszukiwanie binarne, biorąc środkowy element od [l, r], na początku l = 0, r = 3; Biorąc środkowy element, wiesz, ile elementów w tej samej macierzy jest mniejszych, czyli środkowych - 1. Wiedząc, że element środkowy-1 jest mniejszy i wiedząc, że potrzebujesz n-tego elementu, możesz mieć [n - (środkowy-1)] element z drugiej tablicy być mniejszy, większy. Jeśli jest większy i element previos jest mniejszy, to jest to, czego potrzebujesz, jeśli jest większy, a poprzedni jest również większy, musimy L = środek, jeśli jest mniejszy r = środek. Niż to samo dla drugiej macierzy w przypadku, gdy nie znalazłeś rozwiązania na początku. W sumie log (n) + log (n)