Mengapa pencarian biner, yang membutuhkan data yang diurutkan, dianggap lebih baik daripada pencarian linear?

Saya selalu mendengar bahwa pencarian linier adalah pendekatan yang naif dan pencarian biner lebih baik daripada kinerjanya karena kompleksitas asimptotik yang lebih baik. Tapi saya tidak pernah mengerti mengapa ini lebih baik daripada pencarian linear ketika sortasi diperlukan sebelum pencarian biner?

Pencarian linear adalah O(n)dan pencarian biner O(log n). Itu tampaknya menjadi dasar untuk mengatakan bahwa pencarian biner lebih baik. Tetapi pencarian biner membutuhkan pengurutan yang merupakan O(n log n)algoritma terbaik. Jadi pencarian biner seharusnya tidak lebih cepat karena membutuhkan penyortiran.

Saya membaca CLRS di mana penulis menyiratkan bahwa dalam jenis penyisipan daripada menggunakan pendekatan pencarian linear naif, lebih baik menggunakan pencarian biner untuk menemukan tempat di mana item harus dimasukkan. Dalam hal ini ini tampaknya dibenarkan karena pada setiap iterasi loop ada daftar diurutkan di mana pencarian biner dapat diterapkan. Tetapi dalam kasus umum di mana tidak ada jaminan tentang set data yang kita butuhkan untuk mencari tidak menggunakan pencarian biner sebenarnya lebih buruk daripada pencarian linear karena persyaratan pengurutan?

Adakah pertimbangan praktis yang saya abaikan yang menjadikan pencarian biner lebih baik daripada pencarian linear? Atau apakah pencarian biner dianggap lebih baik daripada pencarian linear tanpa mempertimbangkan waktu perhitungan yang diperlukan untuk menyortir?

Adakah pertimbangan praktis yang saya abaikan yang menjadikan pencarian biner lebih baik daripada pencarian linier?

Ya - Anda harus melakukan penyortiran O (n log n) hanya sekali, dan kemudian Anda dapat melakukan pencarian biner O (log n) sesering yang Anda inginkan, sedangkan pencarian linear adalah O (n) setiap kali.

Tentu saja, ini hanya keuntungan jika Anda benar-benar melakukan beberapa pencarian pada data yang sama. Tetapi skenario "menulis sekali, sering membaca" cukup umum.

Asumsi dasarnya adalah bahwa Anda tidak melakukan satu pencarian.

Jadi, jika Anda perlu mencari data yang sama beberapa kali, maka Anda hanya perlu mengurutkan sekali dan dapat mengambil keuntungan dari pencarian biner.

Jika Anda sering mencari dan mengubah data, sebaiknya gunakan daftar yang diurutkan tempat entri baru diurutkan ke dalam daftar.

Jadi pada dasarnya pencarian biner lebih baik ketika Anda mencari daftar yang sama beberapa kali tanpa perlu menggunakan.

Ketika Anda perlu mengurutkan setiap kali sebelum mencari tidak ada keuntungan.

Mohon dicatat bahwa ada algoritma pengurutan yang sangat cepat ketika daftar sudah diurutkan (atau hampir diurutkan). Sebagian besar penentuan kinerja mengharapkan daftar yang tidak disortir.

karena begitu Anda memiliki daftar yang disortir, Anda tidak perlu menyortir ulang setiap kali yang berarti bahwa jika Anda memiliki lebih dari O (log n) pencarian yang mengurutkan di muka akan memberi Anda keuntungan menang ( O(n log n + k log n)vsO(k*n)

Bayangkan dua buku telepon.

Satu buku telepon memiliki nama sesuai urutan abjad. Untuk menemukan entri yang Anda inginkan, Anda buka di tengah, periksa entri, lalu bergerak maju atau mundur tergantung pada apakah Anda melampaui atau kurang.

Buku telepon lainnya memiliki nama-nama dalam urutan acak. Untuk menemukan entri yang Anda inginkan, Anda mulai dari awal dan melanjutkan sampai Anda menemukan apa yang Anda inginkan.

Apakah buku kedua akan berfungsi di kota berukuran wajar?

Saya berpikir bahwa nilai pencarian biner dari pencarian linear adalah kontekstual. Jika Anda mulai dengan kumpulan data tidak teratur yang sangat besar dan hanya berencana untuk mengambil sejumlah kecil item darinya, maka mengurutkan dan melakukan pencarian biner akan lambat. Namun, jika Anda memelihara daftar yang dipesan sepanjang masa aplikasi Anda dan mengaksesnya secara teratur, maka pencarian biner adalah cara yang jauh lebih baik.

Seperti banyak orang lain telah menjawab, pencarian biner memang lebih disukai karena langkah penyortiran dapat dilakukan hanya sekali dan pencarian yang sebenarnya dapat dilakukan sebanyak yang Anda suka. Namun, untuk nilai-nilai n tertentu (yaitu ukuran input tertentu), pencarian biner selalu lebih berkinerja daripada pencarian linear (bahkan untuk sekali jalan tunggal).

"Tipping point" dihitung dengan menyelesaikan persamaan kompleksitas asimptotik:

n log n + log n = n

Seperti yang dapat Anda lihat di Wolfram Alpha, ada nilai numerik untuk n yang memastikan bahwa pencarian biner dan pengurutan selalu lebih cepat daripada pencarian linear saja. Tentu saja nilai aktual dari n yang berfungsi dalam kasus Anda bergantung pada banyak faktor yang mungkin sulit untuk diperkirakan.

Menurut artikel yang menarik dari Mark Probst, yang mencakup beberapa pengukuran kinerja mendalam yang bagus pada prosesor saat ini:

Jika Anda perlu mencari melalui array bilangan bulat yang diurutkan dan kinerjanya sangat, sangat penting, gunakan pencarian linier jika ukuran array Anda di bawah sekitar 64 elemen, pencarian biner jika itu di atas.

Dalam kata-kata awam:

Jika Anda memiliki daftar tidak berurutan dengan sepuluh miliar item, dan item yang kebetulan Anda cari adalah yang terakhir, Anda akhirnya akan membaca sepuluh miliar item.

Dalam kasus pencarian biner, pengindeksan dapat dilakukan sekali saja. Penyisipan kemudian dapat dilakukan di tempat yang tepat untuk menjaga ketertiban.

Sementara banyak alasan bagus untuk "pencarian biner lebih baik" telah terdaftar, kami mungkin juga melihat manfaat dari perspektif pengguna:

Meskipun Anda biasanya dapat hidup dengan sangat baik dengan pemisahan waktu tunggu yang kecil antara tindakan memasukkan data saat Anda melakukan penyisipan yang diurutkan, Anda ingin "mencari" secepat mungkin. Dari sudut pandang pengguna, sisipan yang diurutkan dikombinasikan dengan pencarian biner memberikan pengalaman pengguna sebaik mungkin.