Dlaczego wyszukiwanie binarne nazywa się wyszukiwaniem binarnym?

Słyszałem kilka możliwych wyjaśnień, dlatego chciałbym uzyskać pewne wiarygodne odniesienia.

Aktualizacja 05.19: Interesuje mnie to pytanie, ponieważ jeden z moich studentów napisał w swojej pracy, że nazwa pochodzi od poniższego wyjaśnienia (1). Do tej pory myślałem / słyszałem, że pochodzi z wyjaśnienia (2). Byłoby mi przykro zarówno z powodu pozostawienia niewłaściwej rzeczy w jego pracy magisterskiej, jak i nakłonienia go do usunięcia, jeśli może być słuszna.

(1) Rozważ szukanie liczby całkowitej w przedziale $[0,2^{n-1}]$. Możemy to znaleźć za pomocą$n$ pytania zadawane w kroku $i$ $i^{th}$ cyfra binarna liczby.

(2) Jeśli mamy miejsce wyszukiwania z $2^n$elementów, możemy znaleźć nieznany element poprzez pytania, które wielokrotnie dzielą pozostałą część przestrzeni na dwie części .

I tak, wiem, że (2) może dać ten sam algorytm co (1), ale nie o to tutaj chodzi. (2) można również zastosować w przypadku bardziej ogólnych problemów.

Wyjaśnienie (2) jest dobrym wyjaśnieniem.

(2) jest lepszym wyjaśnieniem tych dwóch elementów, ponieważ dotyczy ogólnie wszystkich zastosowań wyszukiwania binarnego, a nie tylko jednej konkretnej instancji. (1) nie jest nieuzasadnionym sposobem myślenia o tym - po prostu nie jest tak ogólne ani kompletne jak (2).

Nie sądzę, że musisz czuć się zobowiązany do wymagania od ucznia poprawienia tego oświadczenia. Nie byłoby krępujące, gdyby uczeń podał wyjaśnienie (1) w swojej pracy, więc nie musisz się czuć źle. Ale jeśli chcesz ich czegoś nauczyć, możesz powiedzieć im o wyjaśnieniu (2) oraz o tym, w jaki sposób wyszukiwanie binarne jest bardziej ogólne i dlaczego nazwa „wyszukiwanie binarne” jest również uzasadniona dla ogólnego algorytmu. Ale to drobna kwestia, a nie coś, co uważałbym za problematyczne lub zawstydzające, gdyby zostawili rzeczy takimi, jakie są.

Według Wikipedii wyszukiwanie binarne dotyczy wyszukiwania w szeregu posortowanych wartości.

Bardziej ogólna koncepcja wyszukiwania z podziałem i podbijaniem poprzez wielokrotne dzielenie przestrzeni poszukiwań nazywa się wyszukiwaniem dychotomicznym (dosłownie: „to przecina na dwie części”). Zastosowanie dychotomii można rozważyć w innych kontekstach, tak sonn, jak masz coś do podzielenia. To właściwie pierwsze wyrażenie, którego się nauczyłem (myślę, że w liceum i to było dawno temu), także w przypadkach, w których możesz chcieć to nazwać binarnym.

Afaik, „dychotomia” nie oznacza, że ​​obie części są (prawie) równe.

Nie wiem, czy plik binarny jest zarezerwowany do wyszukiwania w przestrzeni wielkości $2^n$.

Dychotomia jest oczywiście terminem bardziej ogólnym, ale może brzmieć pedantycznie dla niektórych, którzy zamiast tego mogliby niewłaściwie używać binarnych.

Twój przykład (1) jest dziwnie określony, ponieważ nie prosi się świadomie o cyfry binarne, ale raczej o porównanie z medianą interwału. Ale może kwalifikować się jako binarny.

Twój przykład (2) jest niejasny. Sam podział na dwie części należy nazwać dychotomicznym. Teraz, gdy wydaje się, że hipotetycznie (dziwnie) sposób tworzenia 2 równych części, nie jestem pewien.

Ale gra polegająca na zgadywaniu, w której ludzie zadają pytania, na które odpowiedź brzmi tak lub nie, jest wyraźnie dychotomiczna.

Moje własne przypuszczenie, brak odniesienia:

Pierwotne wyrażenie było prawdopodobnie „dychotomiczne”, ale wraz z popularnością systemów binarnych, komputera binarnego itp. Termin „binarny” stał się bardziej popularny.

Innym czynnikiem, który mógł odgrywać ważną rolę, jest to, że wyszukiwanie binarne (jak również dychotomiczne) opiera się na wyborach binarnych. Teraz istnieje wyrażenie „ wybór dychotomiczny ”, ale jest znacznie rzadziej używane niż „ wybór binarny ”, który pojawia się około 6 razy częściej w sieci.

To mogło mieć na to wpływ. Powinniśmy pamiętać, że chociaż jesteśmy w dużej mierze zanurzeni w liczbie binarnej (to znaczy my, informatyk), większość ludzi nie jest i nie jest zainteresowana liczbami binarnymi, ale łatwo będzie mówić o wyborze binarnym. Prawdą jest, że wyszukiwanie binarne jest tematem dla informatyków, ale bez wiarygodnego odniesienia do czegoś przeciwnego nie uwierzę, że pochodzi on od liczb binarnych w jakikolwiek bezpośredni sposób.

Knuth (V.3 str. 82) podaje Mauchly jako źródło wyszukiwania binarnego; służy do znalezienia punktu wstawiania podczas sortowania, które następnie przesuwa elementy do przodu w celu utworzenia wolnego miejsca, w procesie zwanym wstawianiem binarnym.

Tak więc (2) byłoby prawidłowe, ale nie widzę oryginalnego papieru; jest tutaj ukryty: https://books.google.com/books?id=A6EEAQAAIAAJ&focus=searchwithinvolume&q=sorting+and+collating

Próbowałem znaleźć odniesienie do Mauchly cytowane przez Knutha, ale moja biblioteka prawdopodobnie zgubiła ich kopię.

W międzyczasie weź pod uwagę następujące wczesne cytaty dotyczące „wyszukiwania binarnego”:

• Halpern, Mark. „ Tabele o zmiennej szerokości z funkcją wyszukiwania binarnego. ” Komunikacja ACM 1.2 (1958): 1-4.

  Rodzina podprogramów opisanych w tym raporcie została zaprojektowana do tworzenia, przeszukiwania i utrzymywania tabel, które mają zawierać wpisy o różnych długościach, a jednocześnie mogą być wyszukiwane według partycji lub wyszukiwania „binarnego”.

• Nagler, H. „ Oszacowanie względnej wydajności dwóch wewnętrznych metod sortowania. ” Komunikat ACM 3.11 (1960): 618-620.

  Niniejszy raport dotyczy IBM 705, modele I i II. Jest to badanie czasu maszynowego wymaganego przez dwie wewnętrzne metody sortowania, konwencjonalne dwukierunkowe scalanie oraz formę wyszukiwania binarnego, która wynika z D. Mordy z IBM Corporation.

• Petersen, TL PROGRAM SYNTEZY POJAZDU. Nr STL / TR-60-0000-09103 (link pdf) . TRW SPACE TECHNOLOGY LABS LOS ANGELES CA, 1960.

  Wartość ${V_0}^*$ dla którego $g({V_0}^*) = 0$trzeba teraz znaleźć. Łatwo to zauważyć$g(0) = K_3 - 1$ i $g(K_1) = -1$, tak aby wymagana wartość ${V_0}^*$ leży między 0 a $K_1$ gdyby $K_3>1$. Przeprowadzane jest wyszukiwanie binarne dla katalogu głównego$g({V_0}^*)$; ${V_0}^*$ wybrana jest ta, dla której bezwzględna wartość różnicy między kolejnymi wartościami ${V_0}^*$ jest mniej niż $0.01$.

Zwrócę uwagę, jak w pierwszym cytacie z 1958 r. Użyto cudzysłowu wokół „binarnego”, ale do trzeciego cytatu z 1960 r. Wspomniano o wyszukiwaniu binarnym bez dalszego opisu lub wyjaśnienia. Aluzja do „wyszukiwania według partycji” sugeruje, że wyjaśnienie 2) jest bliższe, ale wymagana jest dalsza weryfikacja.