Jak mogę lepiej zrozumieć wyszukiwanie binarne za pomocą jednego porównania za każdą z iteracji?

Question

Jaki jest sens wyszukiwania binarnego z jednym porównaniem za iterację? Czy możesz wyjaśnić, jak to działa?

Answer 1

Istnieją dwa powody do wyszukiwania binarnego z jednym porównaniem dla każdej iteracji. The mniej ważne jest wydajność. Wykrywanie dopasowania ścisłego we wczesnych odstępach czasu przy użyciu dwóch porównań na iterację oszczędza średnią iterację pętli, podczas gdy (przy założeniu, że porównania wymagają znacznej pracy) wyszukiwanie binarne z jednym porównaniem na iterację prawie połowę pracy wykonanej dla iteracji.

Binarne przeszukiwanie tablicy liczb całkowitych, prawdopodobnie robi małą różnicę w jedną stronę. Nawet przy dość drogim porównaniu, asymptotycznie wydajność jest taka sama, a połowa raczej niż minusowa prawdopodobnie nie jest warta w większości przypadków. Poza tym kosztowne porównania są często kodowane jako funkcje zwracające wartość ujemną, zerową lub dodatnią dla <, == lub >, dzięki czemu można uzyskać oba porównania za praktycznie dowolną cenę.

Ważnym powodem do wyszukiwania binarnego z jednym porównaniem w iteracji jest , ponieważ można uzyskać bardziej przydatne wyniki niż tylko dopasowanie w przybliżeniu. Głównymi wyszukiwania można zrobić to ...

• Pierwszy klucz> cel
• Pierwszy klucz> = cel
• Pierwszy klucz == celem
• Ostatni klucz < celem
• Ostatni klucz < = cel
• Ostatni klucz == cel

Wszystkie one redukują się do tego samego podstawowego algorytmu. Zrozumienie tego wystarczająco dobrze, że łatwo można zakodować wszystkie warianty nie jest trudne, ale nie widziałem dobrego wyjaśnienia - tylko pseudokodowe i matematyczne dowody. Ta jest moją próbą wyjaśnienia.

Są gry, w których chodzi o to, aby jak najbliżej celu osiągnąć cel bez przestojów. Zmień to na "underershooting", i to właśnie robi "Find First>". Rozważmy zakresy na pewnym etapie wyszukiwania ...

| lower bound  | goal     | upper bound 
+-----------------+-------------------------+-------------- 
|   Illegal | better   worse | 
+-----------------+-------------------------+-------------- 

Zakres między bieżącą górną i dolną granicą nadal musi być przeszukany. Naszym celem jest (normalnie) gdzieś, ale nie wiemy jeszcze gdzie. Interesującym punktem o pozycjach powyżej górnej granicy jest to, że są one zgodne z prawem w w sensie, że są większe niż cel. Można powiedzieć, że pozycja po prostu nad górną granicą jest naszym najlepszym rozwiązaniem. Możemy nawet powiedzieć, że na samym początku jest to , mimo że prawdopodobnie nie ma pozycji w tej pozycji - w sensie , jeśli nie ma poprawnego rozwiązania w zakresie, najlepszym rozwiązaniem, które nie ma było po prostu nieaktualne górna granica.

W każdej iteracji wybieramy element do porównania górnej i dolnej granicy. W przypadku wyszukiwania binarnego jest to zaokrąglony element w połowie. W przypadku wyszukiwania drzewa binarnego jest to podyktowane strukturą drzewa. Zasada jest taka sama w każdym przypadku.

Gdy szukamy produktu większego niż nasz cel, porównujemy testowany przedmiot przy użyciu Item [testpos] > goal. Jeśli wynik jest fałszywy, mamy przekroczony (lub przodozgryz) nasz cel, aby utrzymać naszą najlepszą istniejącą dotychczas rozwiązania i dostosować naszych dolna granica górę. Jeśli wynik jest prawdziwy, znaleźliśmy nowe, najlepsze jak dotąd rozwiązanie , więc dostosowujemy górne ograniczenie, aby to odzwierciedlić.

Tak czy inaczej, nigdy nie chcemy ponownie porównywać tego elementu testowego, więc dostosowujemy nasze , aby wyeliminować (tylko tylko) element testowy z zakresu wyszukiwania. Bycie nieostrożne z tym zwykle skutkuje nieskończonymi pętlami.

Normalnie półotwartych zakresy są używane - integracyjnego dolny i wyłącznym górnej granicy. Korzystanie z tego systemu, element o indeksie górnym oprawionego nie mieści się w zakresie wyszukiwania (przynajmniej nie teraz), ale jest najlepiej dotychczas rozwiązaniem. Kiedy przenieść dolnej granicy w górę, przenieść go do testpos+1 (aby wykluczyć element, który właśnie przetestowany z zakresu). Kiedy przesuniesz górną granicę w dół, przenosisz ją do testowych testów (górna granica i tak jest wyłączna).

if (item[testpos] > goal) 
{ 
    // new best-so-far 
    upperbound = testpos; 
} 
else 
{ 
    lowerbound = testpos + 1; 
} 

Gdy zakres między dolnymi i górnymi granicami jest pusta (za pomocą pół-otwarte, gdy oba mają ten sam indeks), Twój wynik jest swoją najnowszą najlepiej dotychczas rozwiązanie, nieco powyżej górna granica (tj. górny indeks dla półotwartym).

więc pełny algorytm jest ...

while (upperbound > lowerbound) 
{ 
    testpos = lowerbound + ((upperbound-lowerbound)/2); 

    if (item[testpos] > goal) 
    { 
    // new best-so-far 
    upperbound = testpos; 
    } 
    else 
    { 
    lowerbound = testpos + 1; 
    } 
} 

Aby zmienić first key > goal do first key >= goal, dosłownie przełączyć operatora porównania w linii if. Względny operator i cel może zostać zastąpiony przez pojedynczy parametr - funkcję predykatu, która zwraca wartość true, jeśli (i tylko jeśli) jej parametr znajduje się na większej niż docelowa stronie.

który daje "first>" i "Pierwszy> =". Aby uzyskać "first ==", użyj "first> =" i dodaj kontrolę równości po zakończeniu pętli.

Dla "ostatniego <" itp. Zasada jest taka sama jak powyżej, ale zakres jest odczytywany jako . Oznacza to tylko, że zamieniasz się na korekty związane (ale nie komentarz ), a także zmieniasz operatora. Ale zanim to zrobisz, rozważ następujące ...

a > b == !(a <= b) 
a >= b == !(a < b) 

Również ...

• pozycji (ostatni klucz < cel) = pozycja (pierwszy klucz> = cel) - 1
• pozycji (ostatni klucz < = cel) = pozycja (pierwszy klawisz> cel) - 1

Gdy przesuniemy nasze granice podczas wyszukiwania, obie strony są przesuwane w kierunku bramki, dopóki nie spotkają się przy bramce. I znajduje się specjalny element tuż poniżej dolnej granicy, tak jak jest tuż powyżej górnej granicy ...

while (upperbound > lowerbound) 
{ 
    testpos = lowerbound + ((upperbound-lowerbound)/2); 

    if (item[testpos] > goal) 
    { 
    // new best-so-far for first key > goal at [upperbound] 
    upperbound = testpos; 
    } 
    else 
    { 
    // new best-so-far for last key <= goal at [lowerbound - 1] 
    lowerbound = testpos + 1; 
    } 
} 

Więc w pewnym sensie mamy dwie komplementarne wyszukiwania uruchomione jednocześnie. Kiedy spotkają się górne i dolne wejście, mamy użyteczny wynik wyszukiwania po każdej stronie tej jednej granicy.

Dla wszystkich przypadków istnieje szansa, że ​​oryginalna "wyimaginowana" poza najlepszymi pozycjami była ostateczna (w rankingu nie było żadnego dopasowania w zakresie wyszukiwania ). Należy to sprawdzić przed wykonaniem ostatecznego sprawdzenia == dla pierwszych == i ostatnich == przypadków. Może to być również przydatne zachowanie - np. Jeśli szukasz pozycji, w której chcesz wstawić element celu, musisz go dodać, dodając go po końcu swoich istniejących elementów, jeśli wszystkie istniejące elementy są mniejsze niż cel.

Kilka uwag o wyborze testpos ...

testpos = lowerbound + ((upperbound-lowerbound)/2); 

Po pierwsze, to nigdy nie będzie przepełnienie, w przeciwieństwie do bardziej oczywiste ((lowerbound + upperbound)/2). Działa również ze wskaźnikami oraz indeksami całkowitymi .

Po drugie, zakłada się, że podział ma zaokrąglić w dół. Zaokrąglanie w dół dla nie-negatywów jest OK (wszystko, czego możesz być pewny w C), ponieważ różnica jest zawsze nieujemna tak czy inaczej.

Jest to jeden z aspektów, który może wymagać dodatkowej uwagi, jeśli korzystasz z niedomkniętych zakresów - upewnij się, że pozycja testu znajduje się w zakresie wyszukiwania, a nie tylko na zewnątrz (na jednym z już znalezionych najlepiej- dotychczasowe pozycje).

Wreszcie w binarne drzewo poszukiwań, przesuwanie granic jest niejawny i wybór testpos jest wbudowany w strukturę drzewa (które mogą być niesymetryczne), ale te same zasady odnoszą się do tego, co wyszukiwanie jest robić. W przypadku wybieramy nasz węzeł potomny, aby zmniejszyć niejawne zakresy. W przypadku pierwszego meczu przypadków, albo znaleźliśmy nowy, mniejszy najlepszy mecz (przejdź do niższego dziecka, aby znaleźć jeszcze mniejszy i lepszy), albo też przekroczyliśmy limit (przejdź do wyższego dziecka w nadziei na odzyskanie). Ponownie, cztery główne przypadki można obsłużyć, przełączając operatora porównania.

BTW - istnieje więcej możliwych operatorów do użycia dla tego parametru szablonu. Rozważmy tablicę posortowaną według roku, a następnie miesiąca. Może chcesz znaleźć pierwszy przedmiot na dany rok. Aby to zrobić, napisz funkcję porównania, która porównuje rok i ignoruje miesiąc - cel jest porównywany jako równy, jeśli rok jest równy, ale wartość celu może być innego rodzaju niż klucz, który nie ma nawet wartości miesiąca porównać. Uważam to za "częściowe porównanie kluczy" i podłączam je do twojego binarnego szablonu wyszukiwania, a otrzymujesz to, co uważam za "częściowe wyszukiwanie klucza".

EDYCJA W poniższym akapicie użyto określenia "31 grudnia 1999 r. Jako równy 1 lutego 2000". Nie zadziałałoby to, gdyby cały zakres pośredni również nie był równy. Chodzi o to, że wszystkie trzy części dat początku i końca zakresu różnią się, więc nie zajmujesz się kluczem "częściowym", ale klucze uważane za równoważne dla wyszukiwania muszą tworzyć przylegający blok w kontenerze, co zwykle oznacza ciągły blok w uporządkowanym zestawie możliwych kluczy.

Nie jest to też tylko "częściowe" klucze. Twoje porównanie niestandardowe może potrwać do 31 grudnia 1999 r. Jako 1 stycznia 2000 r., Ale wszystkie inne daty będą inne. Chodzi o to, że porównanie niestandardowe musi zgadzać się z oryginalnym kluczem dotyczącym zamawiania, ale może nie być tak wybredne, biorąc pod uwagę różne wartości - może traktować szereg kluczy jako "klasę równoważności".

---

Dodatkowa uwaga na temat granic, które naprawdę powinienem zawrzeć wcześniej, ale może nie pomyślałem o tym w tym momencie.

Jednym ze sposobów myślenia o granicach jest to, że nie są one w całości indeksami pozycji. Związany jest linia graniczna między dwoma elementami, dzięki czemu można ponumerować linie brzegowe tak łatwo, jak można ponumerować elementy ...

|  |  |  |  |  |  |  |  | 
| +-+ | +-+ | +-+ | +-+ | +-+ | +-+ | +-+ | +-+ | 
| |0| | |1| | |2| | |3| | |4| | |5| | |6| | |7| | 
| +-+ | +-+ | +-+ | +-+ | +-+ | +-+ | +-+ | +-+ | 
|  |  |  |  |  |  |  |  | 
0  1  2  3  4  5  6  7  8 

Oczywiście numeracja granic związana jest z numeracją elementów. Dopóki numerujesz od lewej do prawej iw ten sam sposób, w jaki numerujesz swoje przedmioty (w tym przypadku zaczynając od zera), wynik jest faktycznie taki sam, jak w przypadku wspólnej półotwartej konwencji.

Byłoby możliwe wybranie środkowej granicy, aby podzielić zakres dokładnie na dwa, ale nie to robi wyszukiwanie binarne. W przypadku wyszukiwania binarnego wybierasz element do przetestowania - nie związany. Ten przedmiot zostanie przetestowany w tej iteracji i nie wolno go ponownie testować, więc jest wykluczony z obu podzakresów.

|  |  |  |  |  |  |  |  | 
| +-+ | +-+ | +-+ | +-+ | +-+ | +-+ | +-+ | +-+ | 
| |0| | |1| | |2| | |3| | |4| | |5| | |6| | |7| | 
| +-+ | +-+ | +-+ | +-+ | +-+ | +-+ | +-+ | +-+ | 
|  |  |  |  |  |  |  |  | 
0  1  2  3  4  5  6  7  8 
         ^
     |<-------------------|------------->| 
          | 
     |<--------------->| | |<--------->| 
      low range  i  hi range 

Więc testpos i testpos+1 w algorytmie są dwa przypadki tłumaczenia indeks elementu w indeksie związanym. Oczywiście, jeśli te dwa ograniczenia są równe, nie ma żadnych pozycji w tym zakresie do wyboru, więc pętla nie może być kontynuowana, a jedynym możliwym wynikiem jest ta jedna związana wartość.

Przedstawione powyżej zakresy to tylko zakresy do przeszukania - luka, którą zamierzamy zamknąć między sprawdzonymi i niższymi zakresami.

W tym modelu wyszukiwanie binarne wyszukuje granicę między dwoma uporządkowanymi rodzajami wartości - tych zaklasyfikowanych jako "niższe" i tych zaklasyfikowanych jako "wyższe". Test predykatów klasyfikuje jeden element. Nie ma klasy "równej" - wartości równe kluczom są częścią wyższej klasy (dla x[i] >= key) lub klasy niższej (dla x[i] > key).