Czy ten algorytm nadal można uznać za algorytm wyszukiwania binarnego?

14

Podczas wykonywania drugiego kata kodu (który prosi pięć razy o zaimplementowanie algorytmu wyszukiwania binarnego, za każdym razem inną metodą), wpadłem na nieco inne rozwiązanie, które działa w następujący sposób:

Jeśli mam posortowaną tablicę o długości 100 i widzę, że jej pole początkowe zawiera liczbę 200, a pole końcowe zawiera liczbę 400, ja, jako matematyka studiująca człowieka, prawdopodobnie zacznę przeszukiwać pole 35, gdybym szukał liczba 270, a nie pole 50 jak w normalnym algorytmie wyszukiwania binarnego.

Następnie, jeśli liczba w polu 35 tablicy wynosi 270, 35 jest indeksem, którego szukałem.

Jeśli tak nie jest, mogę porównać otrzymaną liczbę (powiedzmy 280) i powtórzyć operację biorąc dolną część tablicy (więc mam 35 pól z polem początkowym zawierającym 200 i polem końcowym zawierającym 280), jeśli liczba, którą znalazłem, jest większa niż to, czego szukam, lub górna część tablicy (powiedzmy, że mam 260: teraz mam 65 indeksów, pierwszy zawiera 260, a ostatni zawiera 400. Orientacyjnie skierowałbym się na torward indeks 4 tej podtablicy, który jest indeksem 39 całej tablicy), jeśli otrzymana liczba jest mniejsza niż liczba, której szukam.

Pytanie brzmi: czy ten algorytm można uznać za algorytm wyszukiwania binarnego? Jeśli nie, to czy ma swoją nazwę?

algorithms terminology search-algorithms binary-search użytkownik6245072
źródło
2
Czy jest to wyszukiwanie binarne, czy nie, wydaje się to wyłącznie kwestią opinii. Zasadniczo jedyną odpowiedzią, jaką możesz udzielić, jest „Tak, jest wystarczająco blisko wyszukiwania binarnego, aby nazwać to wyszukiwaniem binarnym” lub „Nie, to nie jest”. Pojawia się argument.
David Richerby,

Odpowiedzi:

23

Nie nazwałbym tego wyszukiwaniem binarnym.

Jest wyraźnie podobny do wyszukiwania binarnego i naturalne jest postrzeganie go jako udoskonalenia wyszukiwania binarnego. Jednak ma on znacznie różne cechy złożoności algorytmu. Wyszukiwanie interpolacyjne spodziewało się czasu działania O (log (log (n)) przy założeniu, że dane są równomiernie rozmieszczone, jednak płaci za to, mając czas działania O (n) w najgorszym przypadku.

Wolę powiedzieć „Najgorszy czas działania wyszukiwania binarnego to O (log (n))” niż „W zależności od wyboru elementów ograniczających najgorszy czas działania wyszukiwania binarnego to O (log (n))”. Oznacza to, że nie mogę klasyfikować wyszukiwania interpolacyjnego jako algorytmu wyszukiwania binarnego.

Taemyr
źródło
Przypuszczalnie jeśli przerwiesz wyszukiwanie interpolacyjne, gdy idzie źle, możesz zachować O (log n) najgorszy przypadek i O (log log n) na wystarczająco liniowych danych. Domyślam się, że coś w stylu „jeśli nie znalazłem celu po próbie zalogowania się n, to przełącz się na wyszukiwanie binarne” będzie działać, ale jestem zbyt leniwy, aby to udowodnić. Oczywiście będzie istniała klasa zabójczych danych wejściowych, przy czym zajmuje to zasadniczo dwa razy więcej niż wyszukiwanie binarne.
Steve Jessop,
Ten pomysł na zabójcę jest interesujący. Co jeśli zamiast pozwolić zabójczym wejściom negatywnie wpływać na wyszukiwanie (tj. Dzieląc blisko końca tablicy), ograniczamy / przycinamy „dzielny zakres” do drugiej trzeciej części tablicy lub podobnego. Miałoby to najgorszy przypadek log3 (n), ale nadal cieszyłby się najlepszym przypadkiem log (log).
Andrew Gallasch,
1
@ SteveJessop Pamiętaj, że złożoność asymtotyczna nie jest kompletnym obrazem. O (log n) jest bardzo szybki. Ponadto wyszukiwanie binarne działa bardzo mało w każdej pętli. Problem z wyszukiwaniem interpolacji już polega na tym, że potrzebujesz bardzo długich danych wejściowych, aby nadrobić to, że wykonujesz więcej pracy w każdej pętli. Sugestia dodaje do tego więcej pracy. Jeśli nie mogłem zaakceptować O (n) dla danych, które nie były jednolite, podejrzewam, że najlepszym rozwiązaniem jest wybranie czystego wyszukiwania binarnego, a nie jakiegoś hybrydowego podejścia.
Taemyr
@SteveJessop: Nie trzeba przełączać algorytmów; można to zrobić równolegle. Biorąc pod uwagę zakres R, można wyznaczyć punkt P1 jako zwykły punkt środkowy dla wyszukiwania binarnego, a P2 za pomocą interpolacji. Masz teraz trzy podzakresy, z których żaden nie może być większy niż połowa pierwotnego zakresu. Sprawdź wartość docelową zarówno w odniesieniu do P1, jak i P2, a wiesz, w którym z trzech podzakresów ma się powtarzać.
MSalters
17

O(log⁡log⁡n)

Tom van der Zanden
źródło
Chłodny. Teraz pytanie brzmi, czy mogę go użyć do kata kodu, ale to mój problem lol. Uważam to za bardziej skomplikowane niż wyszukiwanie binarne, więc dlaczego nie.
user6245072
Odkryłem to jeden raz, pisząc kod indeksujący plik dziennika kilka lat temu. Odkryłem również, że w przypadku moich danych kroki na przemian między interpolacją a wycinkiem binarnym były lepsze niż każda z opcji. Nie jestem pewien, czy ma to imię, czy jest znanym efektem.
Neil Slater
@NeilSlater zabezpieczone wyszukiwanie interpolacji?
Steve Cox,
@ SteveCox: Właśnie przeszukałem ten termin i nic nie znalazłem. Postanowiłem zadać to jako nowe pytanie: cs.stackexchange.com/questions/59750/…
Neil Slater
-1

Myślę, że poprawną terminologią byłoby rozważenie dychotomialne.

Szukasz w płaskiej tablicy, a następnie rozważasz wyszukiwanie na podstawie przypuszczalnego płaskiego rozkładu liczb.

Odpowiada to temu, jak dana osoba szuka słowa w słowniku. Ale może być bardzo nieefektywne, jeśli rozkład danych jest nieregularny.

Ludovic Zenohate Lagouardette
źródło