Znajdź brakującą 32-bitową liczbę całkowitą wśród nieposortowanych tablic zawierających co najwyżej 4 miliardy int.

Question

To jest problem opisane w Programming pearls. Nie rozumiem metody binarnego wyszukiwania opisanej przez autora. Czy ktoś może pomóc w opracowaniu? Dzięki.

EDYCJA: Rozumiem ogólnie wyszukiwanie binarne. Po prostu nie mogę zrozumieć, jak zastosować wyszukiwanie binarne w tym szczególnym przypadku. Jak zdecydować, brakujący numer znajduje się w pewnym zakresie, abyśmy mogli wybrać inny. Angielski nie jest moim ojczystym językiem, to jeden z powodów, dla których nie potrafię dobrze zrozumieć autora. Tak więc, użyj zwykłego angielskiego proszę :)

EDYCJA: Dziękuję wszystkim za wspaniałą odpowiedź i komentarze! Najważniejszą lekcją, jaką mogę odnieść z rozwiązania tego pytania, jest Wyszukiwanie binarne dotyczy nie tylko posortowanej tablicy!

Answer 1

jest trochę więcej informacji na this web site Cytowany stamtąd..

„to jest pomocne, by zobaczyć tę binarny szukaj w terminach dwudziestu bitów reprezentujących każdą liczbę całkowitą w pierwszym przebiegu algorytmu odczytujemy (najwyżej) milion wejściowych liczb całkowitych i piszemy te z wiodącym bitem zerowym na jedną taśmę i te z wiodącym bitem do innej taśmy. Jedna z tych dwóch taśm zawiera co najwyżej 500 000 liczb całkowitych, więc następnie używamy tej taśmy jako bieżącego wejścia i powtarzamy proces sondy, ale tym razem na drugim bicie. Jeśli oryginalna taśma wejściowa zawiera N elementów, pierwsze przejście odczytuje liczby całkowite N, drugie przejście najwyżej N/2, trzecie przejście co najwyżej N/4, i tak dalej, więc całkowity czas działania jest proporcjonalny do N. brakująca liczba całkowita może zostać znaleziona przez sortowanie na taśmie, a następnie skanowanie, ale wymagałoby to czasu proporcjonalnego do N log N. "

Jak widać, jest to wariacja algorytmu binarnego wyszukiwania: podziel problem na dwie części i rozwiązać problem dla jednego z mniejszych elementów.

Answer 2

Cóż, chodzi o plik zawierający wszystkie 4 miliardy całkowite z wyjątkiem jednego! To jest haczyk w tym przypadku.

1. Podczas poruszania się po liście liczb całkowitych, oblicz sumę.
2. Na koniec oblicz sumę tak, jakby były wszystkie liczby całkowite za pomocą wzoru N * (N + 1)/2
3. Wyodrębnij sumę w (1) z sumy obliczonej w (2). To jest brakująca liczba całkowita.

Przykład: Załóżmy, że mamy następującą sekwencję: 9 3 2 8 4 10 6 1 7 (1 do 10 z 5 brakującymi). Gdy dodamy liczby całkowite sekwencyjnie, otrzymujemy 9 + 3 + 2 + 8 + 4 + 10 + 6 + 1 + 7 = 50. Suma wszystkich liczb całkowitych od 1 do 10 wynosi 10 * (10 + 1)/2 = 55 Dlatego brakująca liczba całkowita to 55 - 50 = 5. QED

Answer 3

Wierzę w to, do czego dąży autor, że wybrałeś środek twojego aktualnego zakresu liczb całkowitych i przygotowałeś dwa pliki wyjściowe. Podczas czytania danych wszystko powyżej punktu środkowego przechodzi do jednego pliku, a wszystko poniżej punktu środkowego przechodzi do drugiego.

Po zakończeniu wybierz mniejszy plik, a następnie powtórz operację, używając [dolnego ograniczenia, środka] lub (punktu środkowego, górnej granicy) jako nowego zakresu, aż plik i zakres są wystarczająco małe aby przełączyć się na wzór bitmapy (lub jeden z Twoich plików wyjściowych jest pusty)

Damien

Answer 4

Ogólna koncepcja: wybierz zakres liczb całkowitych i wybierz wszystkie liczby całkowite mieszczące się w tym przedziale. Jeśli liczba liczb całkowitych jest mniejsza niż wielkość twojego zasięgu, wiesz, że ten zakres zawiera jedną lub więcej brakujących liczb.

Dotyczy to również pierwotnego problemu, ponieważ wiesz, że w niektórych miejscach są również brakujące numery.

Answer 5

Jeśli rozważasz liczby w zakresie od 1 do N; połowa z nich jest większa niż N/2, a połowa z nich jest mniejsza niż N/2

Te większe niż N/2 miałyby MSB ustawiony na jeden; MSB = 0 dla mniejszych.

Partition cały zestaw oparty na MSB który daje dwa zbiory: zbiór liczb mniejszych niż N/2 oraz zestaw liczby większej niż N/2

Partycja mniejsze ma brakujący element .

W następnym kroku użyj następnego MSB.

1. Jeżeli mniejszy zestaw był mniejszy niż N/2, połowa z nich jest mniejsza niż N/4 (2 MSB = 0), a drugą połowę większa od N/4 (2 MSB = 1)

2. Jeśli mniejszy zestaw był większy niż N/2, połowa z nich jest mniejsza niż N/2 + N/4 (2. MSB = 0), a druga połowa większa niż N/2 + N/4 (2. MSB = 1)

Każda runda dzieli o połowę przestrzeń poszukiwań i to wszystko.

Sum (N/2^i) for 0 <= i < log N gives you O(N) 

Answer 6

Jest to w zasadzie to samo pytanie, co this question. To samo podejście działa w przypadku dużej ilości pamięci, aby uzyskać złożoność O (N). Zasadniczo po prostu rekurencyjnie spróbuj umieścić każdą liczbę całkowitą w jej poprawnej lokalizacji i zobacz, co nie ma poprawnej wartości.