Algorytm O (log n) do znalezienia elementu mającego pozycję i w związku z wstępnie sortowanymi listami

Question

Biorąc pod uwagę dwie posortowane listy, każda zawierająca n liczb rzeczywistych, jest algorytm czasu O (log n) do obliczenia elementu rangi i (gdzie odpowiadam indeksowi w porządku rosnącym) w zjednoczeniu dwóch list, zakładając, że elementy obu list są odrębne?

EDYTOWANIE: @BEN: To jest to, co robiłem, ale nadal nie rozumiem.

Mam przykłady;

Lista A: 1, 3, 5, 7 Zestawienie B: 2, 4, 6, 8

Wyszukiwanie stopień (I) = 4

Etap pierwszy: I/2 = 2; Lista A zawiera teraz jest A: 1, 3 Lista B zawiera teraz jest B: 2, 4

  compare A[i] to B[i] i.e 

       A[i] is less; 

       So the lists now become : 

        A: 3 
        B: 2,4 

Krok drugi: I/2 = 1

  List A now contains A:3 
     List B now contains B:2 

     NoW I HAVE LOST THE VALUE 4 which is actually the result ... 

wiem, że brakuje coś, ale nawet po blisko myśleniu nie mogę po prostu wymyślić tego ...

Answer 1

Tak:

Wiesz element leży w każdym indeksie [0,i] z pierwszej listy lub [0,i] z drugiej listy. Weź element i/2 z każdej listy i porównaj. Kontynuuj przez bisection.

Nie dołączam żadnego kodu, ponieważ ten problem brzmi bardzo jak zadanie domowe.

EDYCJA: Bisection jest metodą kryjącą się za wyszukiwaniem binarnym.Działa to tak:

Załóżmy i = 10; (indeksowanie od zera, szukamy 11 elementu ogólnie).

W pierwszym kroku wiadomo, że odpowiedź znajduje się na liście 1 (0 ... 10) lub na liście 2 (0 ... 10). Take a = list1 (5) i b = list2 (5).

Jeśli a> b, to na liście 1 znajduje się 5 elementów, które występują przed a, i co najmniej 6 elementów na liście2, które pojawiają się przed a. A więc jest górną granicą wyniku. Podobnie jest 5 elementów na liście2, które pochodzą przed b i mniej niż 6 elementów na liście1, które pochodzą przed b. Zatem b jest dolną granicą wyniku. Teraz wiemy, że wynik znajduje się na liście 1 (0..5) lub na liście2 (5..10). Jeśli jest to < b, wynikiem jest lista1 (5..10) lub lista2 (0..5). A jeśli a == b mamy naszą odpowiedź (ale problem mówi, że elementy były różne, dlatego a! = B).

Powtarzamy ten proces, zmniejszając rozmiar przestrzeni wyszukiwania o połowę przy każdym kroku. Bisekcja odnosi się do faktu, że wybieramy środkowy element (dwusieczną) poza zasięgiem, który znamy z wynikiem.

Jedyna różnica między tą i binarną wyszukiwarką polega na tym, że w wyszukiwaniu binarnym porównujemy ją z wartością, której szukamy, ale tutaj porównujemy wartość z drugiej listy.

UWAGA: w rzeczywistości jest to O(log i), który jest lepszy (przynajmniej nie gorszy niż) niż O(log n). Co więcej, dla małych i (prawdopodobnie i100), faktycznie mniej operacji będzie scalać pierwsze i elementy (wyszukiwanie liniowe zamiast bisekcji), ponieważ jest to o wiele prostsze. Po dodaniu zachowania pamięci podręcznej i lokalizacji danych wyszukiwanie liniowe może być szybsze nawet o kilka tysięcy.

Ponadto, jeśli i> n następnie powoływać się na fakt, że wynik ma być pod koniec każdej listy, początkowy zakres kandydat w każdym liście jest z ((w) .. n)

Answer 2

Podczas łączenia dwóch list, będziesz musiał dotknąć każdego elementu na obu listach. Jeśli nie dotkniesz każdego elementu, niektóre elementy pozostaną w tyle. Zatem twoja teoretyczna dolna granica to O (n). Więc nie możesz tego zrobić w ten sposób.

Nie musisz sortować, ponieważ masz już dwie listy, które są już posortowane, i możesz zachować tę kolejność jako część scalenia.

Answer 3

edytuj: oops, błędnie przeczytałem pytanie. Myślałem, że podana wartość, chcesz znaleźć pozycję, a nie odwrotnie. Jeśli chcesz znaleźć rangi daną wartość, to jest, jak to zrobić w O(log N):

Tak, można to zrobić w O(log N), jeżeli lista umożliwia O(1) dostępie swobodnym (czyli jest to tablica, a nie związane lista).

• Binary wyszukiwania na L1
• Binary wyszukiwania na L2
• Suma indeksy

Trzeba wypracować matematyki, +1, -1, co zrobić, jeśli elementem nie znaleziono itd., ale taki jest pomysł.

Answer 4

Tutaj to jak to robisz.

Niech pierwsza lista będzie ListX, a druga lista będzie ListY. Musimy znaleźć odpowiednią kombinację ListX[x] i ListY[y] gdzie x + y = i. Ponieważ x, y, i są liczbami naturalnymi, możemy od razu ograniczyć naszą domenę problemową do x*y. I używając równań max(x) = len(ListX) i max(y) = len(ListY) mamy teraz podzbiór elementów x*y w postaci [x, y], które musimy przeszukać.

Co należy zrobić, to zamówić te elementy, takie jak: [i - max(y), max(y)], [i - max(y) + 1, max(y) - 1], ..., [max(x), i - max(x)]. Następnie podzielisz tę listę na drugą, wybierając środkową kombinację [x, y]. Ponieważ listy są uporządkowane i różne, możesz przetestować ListX[x] < ListY[y]. Jeśli jest to prawda, dzielimy górną połowę naszych kombinacji [x, y] lub jeśli są fałszywe, dzielimy dolną połowę. Będziesz ciągle bisecting, aż znajdziesz właściwą kombinację.

Zostało wiele szczegółów, ale to jest ogólny sens tego. To rzeczywiście jest O (log (n))!

Edytuj: Jak Ben wskazał to faktycznie O(log(i)). Jeśli wpuścimy n = len(ListX) + len(ListY), to wiemy, że i <= n.