Bisakah algoritma ini masih dianggap sebagai algoritma Pencarian Biner?

14

Saat melakukan kata kode kedua (yang meminta Anda untuk menerapkan algoritma pencarian biner lima kali, setiap kali dengan metode yang berbeda), saya telah menghasilkan solusi yang sedikit berbeda yang berfungsi sebagai berikut:

Jika saya memiliki array yang disortir dengan panjang 100 dan saya melihat bidang awalnya berisi angka 200 dan bidang akhirnya berisi angka 400, saya, sebagai matematika yang mempelajari manusia, kemungkinan akan mulai mencari di sekitar bidang 35 jika saya mencari di angka 270, dan bukan bidang 50 seperti dalam algoritma pencarian biner normal.

Kemudian, jika angka pada bidang 35 array adalah 270, 35 adalah indeks yang saya cari.

Jika bukan itu masalahnya saya dapat membandingkan angka yang saya dapatkan (katakanlah 280) dan ulangi operasi dengan mengambil bagian bawah array (jadi saya memiliki 35 bidang dengan bidang awal berisi 200 dan bidang akhir berisi 280) jika nomor yang saya temukan lebih besar dari apa yang saya cari, atau bagian atas array (katakan saya mendapat 260: sekarang saya memiliki 65 indeks, yang pertama berisi 260 dan yang terakhir berisi 400). Orientatif, saya akan menuju ke atas indeks 4 dari sub array ini, yang merupakan indeks 39 dari seluruh array) jika angka yang saya dapatkan lebih kecil dari angka yang saya cari.

Pertanyaannya adalah: dapatkah algoritma ini dianggap sebagai algoritma pencarian biner? Jika tidak, apakah sudah mendapat namanya sendiri?

algorithms terminology search-algorithms binary-search pengguna6245072
sumber
2
Entah itu pencarian biner atau tidak, sepertinya ini semata-mata masalah pendapat. Pada dasarnya, satu-satunya jawaban yang dapat Anda berikan adalah "Ya, itu cukup dekat dengan pencarian biner untuk menyebutnya pencarian biner" atau "Tidak, tidak." Terjadi pertengkaran.
David Richerby

Jawaban:

23

Saya tidak akan menyebut ini pencarian biner.

Ini jelas mirip dengan pencarian biner dan wajar untuk melihatnya sebagai penyempurnaan dari pencarian biner. Namun memiliki karakteristik kompleksitas algoritma yang berbeda secara signifikan, Pencarian Interpolasi telah memperkirakan waktu berjalan O (log (log (n)) dengan asumsi data terdistribusi secara seragam, namun membayar untuk ini dengan memiliki O (n) waktu menjalankan kasus terburuk.

Saya lebih suka mengatakan "Waktu run kasus terburuk dari pencarian biner adalah O (log (n))" daripada "Tergantung pada pilihan elemen pembatas, run time case terburuk dari pencarian biner adalah O (log (n))". Ini berarti bahwa saya tidak dapat mengklasifikasikan pencarian Interpolasi sebagai algoritma pencarian biner.

Taemyr
sumber
Agaknya jika Anda keluar dari pencarian interpolasi ketika sedang buruk, Anda dapat mempertahankan O (log n) kasus terburuk dan O (log log n) pada data linear yang cukup. Dugaan saya adalah sesuatu seperti "jika saya belum menemukan target setelah mencoba dan mencoba beralih ke pencarian biner" akan berhasil, tetapi saya terlalu malas untuk membuktikannya. Tentu saja akan ada kelas input pembunuh yang pada dasarnya ini membutuhkan dua kali lebih lama dari pencarian biner.
Steve Jessop
Gagasan input pembunuh itu menarik. Bagaimana jika alih-alih membolehkan input pembunuh memengaruhi pencarian secara negatif (yaitu dengan memisahkan di dekat akhir array), kami membatasi / memangkas "rentang yang dapat dipisah" hingga sepertiga ke-2 array atau serupa. Itu akan memiliki log3 kasus terburuk (n) tetapi masih menikmati log (log) kasus terbaik.
Andrew Gallasch
1
@SteveJessop Ingatlah bahwa kompleksitas asimtotik bukanlah gambaran lengkap. O (log n) sangat cepat. Selain itu pencarian biner bekerja sangat sedikit di setiap loop. Jadi sudah masalah untuk pencarian Interpolasi adalah bahwa Anda memerlukan input yang sangat panjang untuk menebus fakta bahwa Anda melakukan lebih banyak pekerjaan pada setiap loop. Saran Anda menambahkan lebih banyak pekerjaan untuk itu. Jika saya tidak dapat menerima O (n) untuk data yang tidak seragam, saya kira solusi terbaik adalah pergi untuk pencarian Biner murni, daripada beberapa pendekatan hybrid.
Taemyr
@SteveJessop: Tidak perlu berganti algoritma; ini bisa dilakukan secara paralel. Dengan rentang R, Anda dapat menentukan titik P1 sebagai titik tengah biasa untuk pencarian biner, dan P2 menggunakan interpolasi. Anda sekarang memiliki tiga subranges, tidak ada yang bisa lebih besar dari setengah rentang aslinya. Periksa nilai target terhadap P1 dan P2, dan Anda tahu yang mana dari tiga subrang untuk recurse.
MSalters
17

Ya, ini dikenal sebagai Pencarian Interpolasi . Dengan beberapa peringatan (tergantung pada model komputasi Anda dan distribusi data) waktu berjalan yang diharapkan adalah , lebih baik daripada pencarian biner.O(log⁡log⁡n)

Tom van der Zanden
sumber
Keren. Sekarang pertanyaannya adalah apakah saya bisa menggunakannya untuk kode kata, tapi ini masalah saya lol. Saya menemukan ini lebih rumit daripada pencarian biner jadi mengapa tidak.
user6245072
Saya menemukan ini satu kali ketika menulis kode untuk mengindeks file log beberapa tahun yang lalu. Saya juga menemukan bahwa untuk data saya, bergantian langkah-langkah antara interpolasi dan irisan biner lebih baik daripada kedua opsi itu sendiri. Saya tidak yakin apakah itu memiliki nama, atau efek yang diketahui.
Neil Slater
@NeilSlater mungkin lindung nilai pencarian interpolasi mungkin?
Steve Cox
@SteveCox: Saya baru saja mencari istilah itu dan tidak menemukan apa pun. Memutuskan untuk menanyakan hal itu sebagai pertanyaan baru: cs.stackexchange.com/questions/59750/...
Neil Slater
-1

Saya pikir terminologi yang benar akan menjadi pencarian yang direnungkan dikotomial.

Anda mencari dalam susunan datar dengan pencarian yang direnungkan selanjutnya berdasarkan pada distribusi rata yang seharusnya dari angka-angka di dalamnya.

Ini sesuai dengan bagaimana seseorang akan mencari kata dalam kamus. Tetapi bisa sangat tidak efisien jika distribusi data tidak teratur.

Ludovic Zenohate Lagouardette
sumber