Algoritma Pencarian Biner: Fungsi, Manfaat, Kompleksitas Waktu & Ruang

pengantar

Dalam sistem komputasi apapun, pencarian adalah salah satu fungsi yang paling penting untuk dikembangkan. Teknik pencarian digunakan dalam pengambilan file, pengindeksan, dan banyak aplikasi lainnya. Ada banyak teknik pencarian yang tersedia. Salah satunya adalah teknik pencarian biner.

Algoritma pencarian biner bekerja berdasarkan gagasan untuk mengabaikan setengah dari daftar pada setiap iterasi. Itu terus membelah daftar sampai menemukan nilai yang dicarinya dalam daftar yang diberikan. Sebuah algoritma pencarian biner adalah upgrade cepat ke algoritma pencarian linier sederhana.

Tidak Diperlukan Pengalaman Pengkodean. Dukungan karir 360°. Diploma PG dalam Pembelajaran Mesin & AI dari IIIT-B dan upGrad.

Bekerja dari Algoritma Pencarian Biner

Hal pertama yang perlu diperhatikan adalah bahwa algoritma pencarian biner selalu bekerja pada daftar yang diurutkan. Oleh karena itu langkah logis pertama adalah mengurutkan daftar yang disediakan. Setelah menyortir, median daftar diperiksa dengan nilai yang diinginkan.

• Jika nilai yang diinginkan sama dengan nilai indeks pusat, maka indeks dikembalikan sebagai jawaban.

• Jika nilai target lebih rendah dari kesepakatan indeks pusat dari daftar, maka sisi kanan daftar diabaikan.

• Jika nilai yang diinginkan lebih besar dari nilai indeks pusat, maka bagian kiri dibuang.

• Proses ini kemudian diulang pada daftar pendek sampai nilai target ditemukan.

Contoh 1

Mari kita lihat algoritma dengan sebuah contoh. Asumsikan ada daftar dengan nomor berikut:

1, 15, 23, 7, 6, 14, 8, 3, 27

Mari kita ambil nilai yang diinginkan sebagai 27. Jumlah total elemen dalam daftar adalah 9.

Langkah pertama adalah mengurutkan daftar. Setelah diurutkan, daftarnya akan terlihat seperti ini:

1, 3, 6, 7, 8, 14, 15, 23, 27

Karena jumlah elemen dalam daftar adalah sembilan, indeks pusat akan menjadi lima. Nilai pada indeks lima adalah 8. Nilai yang diinginkan, 27, dibandingkan dengan nilai 8. Pertama, periksa apakah nilainya sama dengan 8 atau tidak. Jika ya, kembalikan indeks dan keluar.

Karena 27 lebih besar dari 8, kita akan mengabaikan bagian kiri dan hanya melintasi sisi kanan daftar. Daftar baru yang harus dilintasi adalah:

14, 15, 23, 27

Catatan: Dalam praktiknya, daftar tidak terpotong. Hanya pengamatan yang dipersempit. Jadi, "daftar baru" tidak boleh disamakan dengan membuat daftar baru atau memperpendek yang asli. Meskipun bisa diimplementasikan dengan daftar baru, ada dua masalah. Pertama, akan ada overhead memori. Setiap daftar baru akan meningkatkan kompleksitas ruang. Dan kedua, indeks asli perlu dilacak pada setiap iterasi.

Indeks pusat baru dapat diambil sebagai elemen kedua atau ketiga, tergantung pada implementasinya. Di sini, kita akan mempertimbangkan elemen ketiga sebagai pusat. Nilai 23 dibandingkan dengan nilai 27. Karena nilainya lebih besar dari nilai pusat, kita akan membuang setengah bagian kiri.

Daftar yang harus dilalui adalah:

27

Karena daftar hanya berisi satu elemen, itu dianggap sebagai elemen pusat. Oleh karena itu, kami membandingkan nilai yang diinginkan dengan 27. Saat mereka cocok, kami mengembalikan nilai indeks 27 dalam daftar asli.

Contoh #2

Dalam daftar yang sama, mari kita asumsikan nilai yang diinginkan adalah 2.

Pertama, nilai pusat delapan dibandingkan dengan 2. Karena nilai yang diinginkan lebih kecil dari nilai pusat, kami mempersempit fokus kami ke sisi kiri daftar.

Lintasan baru akan terdiri dari:

1, 3, 6, 7

Mari kita ambil elemen pusat sebagai elemen kedua. Nilai dua yang diinginkan dibandingkan dengan 3. Karena nilainya masih lebih kecil, kami kembali mempersempit fokus ke sisi kiri daftar.

Lintasan baru akan terdiri dari:

1

Karena daftar traversing hanya memiliki satu elemen, nilainya langsung dibandingkan dengan elemen yang tersisa. Kami melihat bahwa nilainya tidak cocok. Oleh karena itu, kami keluar dari loop dengan pesan kesalahan: v alue not found .

Sertifikasi Tingkat Lanjut Ilmu Data, 250+ Mitra Perekrutan, 300+ Jam Pembelajaran, 0% EMI

Kompleksitas Ruang dan Waktu

Kompleksitas waktu dari algoritma pencarian biner adalah O(log n). Kompleksitas waktu kasus terbaik adalah O(1) ketika indeks pusat akan langsung cocok dengan nilai yang diinginkan. Skenario terburuk dapat berupa nilai di ujung daftar atau nilai yang tidak ada dalam daftar.

Kompleksitas ruang dari algoritma pencarian biner tergantung pada implementasi dari algoritma tersebut. Ada dua cara untuk mengimplementasikannya:

1. Metode berulang
2. Metode rekursif

Kedua metode ini hampir sama, dengan dua perbedaan dalam penerapannya. Pertama, tidak ada loop dalam metode rekursif. Kedua, alih-alih meneruskan nilai baru ke iterasi loop berikutnya, ia meneruskannya ke rekursi berikutnya. Pada metode iteratif, iterasi dapat dikontrol melalui kondisi perulangan, sedangkan pada metode rekursif digunakan kondisi batas maksimum dan minimum.

Dalam metode iteratif, kompleksitas ruang akan menjadi O(1). Sedangkan pada metode rekursif, kompleksitas ruang akan menjadi O(log n).

Manfaat

• Algoritma pencarian biner adalah algoritma pencarian yang cukup sederhana untuk diterapkan.

• Ini adalah peningkatan yang signifikan atas pencarian linier dan melakukan hampir sama dibandingkan dengan beberapa algoritma pencarian yang lebih sulit untuk diterapkan.

• Algoritma pencarian biner memecah daftar menjadi dua pada setiap iterasi, daripada menyisir daftar secara berurutan. Pada daftar besar, metode ini bisa sangat berguna.

Checkout: Klasifikasi Pohon Keputusan: Semua yang Perlu Anda Ketahui

Kesimpulan

Sebuah algoritma pencarian biner adalah algoritma yang banyak digunakan dalam domain komputasi. Ini adalah algoritme pencarian yang gemuk dan akurat yang dapat bekerja dengan baik pada kumpulan data besar dan kecil. Algoritma pencarian biner adalah algoritma yang sederhana dan dapat diandalkan untuk diterapkan. Dengan analisis waktu dan ruang, manfaat menggunakan teknik khusus ini menjadi jelas.

Jika Anda penasaran untuk belajar tentang ilmu data, lihat Diploma PG IIIT-B & upGrad dalam Ilmu Data yang dibuat untuk para profesional yang bekerja dan menawarkan 10+ studi kasus & proyek, lokakarya praktis, bimbingan dengan pakar industri, 1- on-1 dengan mentor industri, 400+ jam pembelajaran dan bantuan pekerjaan dengan perusahaan-perusahaan top.