Mengapa pencarian biner disebut pencarian biner?

Saya mendengar beberapa penjelasan yang mungkin, jadi saya ingin referensi yang dapat dipercaya.

Pembaruan 05.19: Saya tertarik dengan pertanyaan itu karena salah seorang siswa saya menulis dalam tesisnya bahwa nama tersebut berasal dari penjelasan di bawah ini (1). Sampai sekarang saya berpikir / mendengar bahwa itu berasal dari penjelasan (2). Saya akan merasa sedih karena membiarkan hal yang salah dalam tesisnya, serta menyuruhnya untuk menghapusnya jika itu mungkin benar.

(1) Pertimbangkan pencarian bilangan bulat dalam interval . Kita dapat menemukannya menggunakan n pertanyaan dengan bertanya pada langkah i yang i t h biner digit dari nomor tersebut.$[0,2^{n-1}]$$n$$i$$i^{th}$

(2) Jika kami memiliki ruang pencarian dengan elemen , kami dapat menemukan elemen yang tidak diketahui dengan pertanyaan yang berulang kali membagi bagian ruang yang tersisa menjadi dua .$2^n$

Dan ya, saya tahu bahwa (2) dapat memberikan algoritma yang sama dengan (1) tetapi bukan itu intinya di sini. (2) dapat juga diterapkan untuk masalah yang lebih umum.

Penjelasan (2) adalah penjelasan yang baik.

(2) adalah penjelasan yang lebih baik dari keduanya, karena itu berlaku secara umum untuk semua penggunaan pencarian biner, bukan hanya satu contoh spesifik. (1) bukan cara yang tidak masuk akal untuk memikirkannya - hanya saja tidak umum atau selengkap (2).

Saya tidak berpikir Anda perlu merasa wajib untuk meminta siswa untuk memperbaiki pernyataan ini. Tidak akan memalukan jika seorang siswa memberikan penjelasan (1) dalam tesis mereka, jadi Anda tidak perlu merasa buruk. Tetapi jika Anda ingin mengajari mereka sesuatu, Anda dapat memberi tahu mereka tentang penjelasan (2) dan tentang bagaimana pencarian biner lebih umum dan mengapa nama "pencarian biner" juga masuk akal untuk algoritma umum. Tetapi ini adalah hal kecil dan bukan sesuatu yang saya anggap bermasalah atau memalukan jika mereka membiarkannya.

Menurut Wikipedia, pencarian biner menyangkut pencarian dalam array nilai yang diurutkan.

Konsep yang lebih umum dari pencarian membagi dan menaklukkan dengan berulang kali membagi ruang pencarian disebut pencarian dikotomik (secara harfiah: "yang memotong dua"). Penggunaan dikotomi dapat dipertimbangkan dalam konteks lain, sama seperti Anda memiliki sesuatu untuk dibagi. Ini sebenarnya ungkapan pertama yang saya pelajari (di sekolah menengah, saya kira, dan itu sudah lama sekali), termasuk dalam kasus di mana Anda mungkin ingin menyebutnya biner.

Afaik, "dikotomik" tidak menyiratkan bahwa kedua bagian itu (hampir) sama.

Saya tidak tahu bahwa biner disediakan untuk mencari dalam ruang ukuran $2^n$

Dichotomic jelas merupakan istilah yang lebih umum, tetapi mungkin terdengar membingungkan bagi sebagian orang yang mungkin menggunakan biner secara tidak tepat.

Contoh Anda (1) secara aneh dinyatakan, karena seseorang tidak secara sadar meminta angka biner, melainkan untuk perbandingan dengan median dari suatu interval. Tapi itu bisa disebut sebagai biner.

Contoh Youe (2) tidak jelas. Membagi menjadi dua harus disebut dikotomik. Sekarang, ketika Anda tampaknya menghipotesiskan (anehnya) cara membuat 2 bagian yang sama, saya tidak yakin.

Tapi permainan menebak, di mana orang-orang mengajukan pertanyaan yang dijawab dengan ya atau tidak jelas dikotomik.

Tebakan saya sendiri, tidak ada referensi yang diberikan:

Ungkapan asli mungkin "dikotomik", tetapi dengan popularitas sistem biner, komputer biner, dll, istilah "biner" menjadi lebih populer.

Salah satu faktor lain yang mungkin memainkan peran penting adalah pencarian biner (dan juga dikotomik) didasarkan pada pilihan biner. Sekarang ungkapan " pilihan dikotomis " memang ada, tetapi jauh lebih sedikit digunakan daripada " pilihan biner ", yang muncul sekitar 6 kali lebih sering di web.

Jadi ini mungkin mempengaruhi hal itu. Kita harus ingat bahwa meskipun kita sebagian besar terbenam dalam bilangan biner (maksud saya kita, ilmuwan komputer), kebanyakan orang tidak dan tidak peduli dengan bilangan biner, tetapi akan dengan mudah berbicara tentang pilihan biner. Memang benar bahwa pencarian biner adalah topik untuk ilmuwan komputer, tetapi pendek referensi yang dapat diandalkan sebaliknya saya tidak akan percaya itu berasal dari angka biner dengan cara langsung.

Knuth (V.3 Pg. 82) memberikan Mauchly sebagai sumber untuk pencarian biner; ini digunakan untuk menemukan titik penyisipan selama pengurutan yang kemudian menggerakkan elemen ke depan untuk membuat lowongan, dalam proses yang disebut penyisipan biner.

Jadi (2) akan valid, tetapi saya tidak bisa melihat kertas aslinya; itu dikaburkan di sini: https://books.google.com/books?id=A6EEAQAAIAAJ&focus=searchwithinvolume&q=sorting+and+collating

Saya mencoba mencari referensi Mauchly yang dikutip oleh Knuth tetapi perpustakaan saya tampaknya telah salah menempatkan salinan mereka.

Sementara itu, pertimbangkan kutipan awal-ish berikut untuk "pencarian biner":

• Halpern, Mark. " Tabel lebar variabel dengan fasilitas pencarian biner. " Komunikasi ACM 1.2 (1958): 1-4.

  Keluarga subrutin yang dijelaskan dalam laporan ini dirancang untuk membuat, mencari dan memelihara tabel yang berisi entri dengan panjang yang berbeda, namun harus dapat dicari berdasarkan partisi, atau pencarian "biner".

• Nagler, H. " Perkiraan efisiensi relatif dua metode penyortiran internal. " Komunikasi ACM 3.11 (1960): 618-620.

  Laporan ini menyangkut IBM 705, model I dan II. Ini adalah studi tentang waktu mesin yang diperlukan oleh dua metode penyortiran internal, penggabungan dua arah konvensional, dan bentuk pencarian biner, yang disebabkan oleh D. Mordy, dari IBM Corporation.

• Petersen, TL PROGRAM SINTESIS KENDARAAN ENTRI KEMBALI Tidak. STL / TR-60-0000-09103 (tautan pdf) . TRW SPACE TECHNOLOGY LABS LOS ANGELES CA, 1960.

  ${V_0}^*$$g({V_0}^*) = 0$$g(0) = K_3 - 1$$g(K_1) = -1$${V_0}^*$$K_1$$K_3>1$$g({V_0}^*)$${V_0}^*$${V_0}^*$$0.01$

Saya akan mencatat bagaimana kutipan tahun 1958 pertama menggunakan tanda kutip di sekitar "biner" tetapi pada kutipan ketiga pada tahun 1960, pencarian biner disebutkan tanpa deskripsi atau penjelasan lebih lanjut. Alusi untuk "mencari berdasarkan partisi" cenderung menyarankan bahwa penjelasan 2) lebih dekat, tetapi verifikasi lebih lanjut diperlukan.