Algoritma Pencarian Biner dengan CONTOH

Sebelum mempelajari pencarian biner, mari kita pelajari terlebih dahulu apa itu pencarian.

Apa itu Pencarian?

Pencarian adalah utilitas yang memungkinkan penggunanya menemukan dokumen, file, media, atau jenis data lain apa pun yang disimpan di dalam database. Pencarian bekerja berdasarkan prinsip sederhana yaitu mencocokkan kriteria dengan catatan dan menampilkannya kepada pengguna. Dengan cara ini, fungsi pencarian paling dasar berfungsi.

Apa itu Pencarian Biner?

Pencarian biner adalah jenis algoritma pencarian tingkat lanjut yang menemukan dan mengambil data dari daftar item yang telah diurutkan. Prinsip kerja intinya melibatkan pembagian data dalam daftar menjadi dua hingga nilai yang dibutuhkan ditemukan dan ditampilkan kepada pengguna dalam hasil pencarian. Pencarian biner umumnya dikenal sebagai... pencarian setengah interval atau pencarian logaritmik.

Bagaimana Pencarian Biner Bekerja?

Pencarian biner bekerja dengan cara berikut:

• Proses pencarian dimulai dengan menemukan elemen tengah dari larik data yang telah diurutkan.
• Setelah itu, nilai kunci dibandingkan dengan elemen tersebut.
• Jika nilai kunci lebih kecil daripada elemen tengah, maka pencarian akan menganalisis nilai-nilai di atas elemen tengah untuk perbandingan dan pencocokan.
• Jika nilai kunci lebih besar dari elemen tengah, maka pencarian akan menganalisis nilai yang lebih rendah terhadap elemen tengah untuk perbandingan dan pencocokan.

Algoritma Pencarian Biner (Pseudokode)

Pencarian biner dapat ditulis sebagai rutinitas iteratif yang singkat. Rutinitas ini menyimpan dua pointer, rendah dan tinggi, dan mempersempit rentang hingga target ditemukan atau rentang menjadi kosong.

binarySearch(array, target)
    low = 0
    high = length(array) - 1
    while low <= high
        mid = (low + high) / 2      // floor value
        if array[mid] == target
            return mid
        else if array[mid] < target
            low = mid + 1
        else
            high = mid - 1
    return -1              // target not found

Rutinitas ini mengembalikan indeks target jika berhasil dan -1 jika nilainya tidak ada. Karena rentangnya berkurang setengah pada setiap putaran, loop berjalan paling banyak log₂(n) kali.

Contoh Pencarian Biner

Mari kita lihat contoh kamus. Jika Anda perlu mencari kata tertentu, tidak ada yang menelusuri setiap kata secara berurutan, tetapi secara acak mencari kata terdekat untuk mencari kata yang dibutuhkan.

Gambar di atas mengilustrasikan hal berikut:

1. Anda memiliki array 10 digit, dan elemen 59 perlu ditemukan.
2. Semua elemen ditandai dengan indeks dari 0 hingga 9. Sekarang, nilai tengah array dihitung. Untuk melakukannya, ambil nilai paling kiri dan paling kanan dari indeks tersebut dan bagi dengan 2. Hasilnya adalah 4.5, tetapi kita ambil nilai pembulatan ke bawah (floor). Oleh karena itu, nilai tengahnya adalah 4.
3. Algoritma tersebut menghilangkan semua elemen dari tengah (4) ke batas terendah, karena 59 lebih besar dari 24, dan sekarang array hanya tersisa dengan 5 elemen.
4. Sekarang, 59 lebih besar dari 45 dan kurang dari 63. Angka tengahnya adalah 7. Oleh karena itu, nilai indeks kanan menjadi tengah − 1, yang sama dengan 6, dan nilai indeks kiri tetap sama seperti sebelumnya, yaitu 5.
5. Pada titik ini, Anda tahu bahwa 59 muncul setelah 45. Oleh karena itu, indeks kiri, yaitu 5, juga menjadi pertengahan.
6. Iterasi ini berlanjut hingga array direduksi menjadi hanya satu elemen, atau item yang ditemukan menjadi bagian tengah array.

Contoh 2

Mari kita lihat contoh berikut untuk memahami cara kerja pencarian biner.

1. Anda memiliki larik nilai yang diurutkan mulai dari 2 hingga 20 dan perlu menemukan 18.
2. Rata-rata batas bawah dan batas atas adalah (l + r) / 2 = 4. Nilai yang dicari lebih besar dari nilai tengah, yaitu 4.
3. Nilai-nilai dalam array yang kurang dari nilai tengah akan dihilangkan dari pencarian, dan nilai-nilai yang lebih besar dari nilai tengah (4) akan dicari.
4. Ini adalah proses pembagian yang berulang hingga item sebenarnya yang akan dicari ditemukan.

Mengapa Kita Membutuhkan Pencarian Biner?

Berikut ini beberapa alasan mengapa pencarian biner merupakan pilihan yang lebih baik untuk digunakan sebagai algoritma pencarian:

• Pencarian biner bekerja secara efisien pada data yang sudah diurutkan, berapa pun ukuran datanya.
• Alih-alih melakukan pencarian dengan menelusuri data secara berurutan, algoritma biner mengakses data secara acak untuk menemukan elemen yang diperlukan. Hal ini membuat siklus pencarian menjadi lebih pendek dan akurat.
• Pencarian biner melakukan perbandingan data yang diurutkan berdasarkan prinsip pengurutan, bukan menggunakan perbandingan kesamaan, yang lebih lambat dan sebagian besar tidak akurat.
• Setelah setiap siklus pencarian, algoritma membagi ukuran array menjadi dua; oleh karena itu, pada iterasi berikutnya, algoritma hanya akan bekerja pada setengah bagian array yang tersisa.

Pelajari tutorial kami selanjutnya tentang Pencarian Linier: Python, C++ Example.

Pencarian Biner vs Pencarian Linier

Pencarian biner dan pencarian linier adalah dua cara paling umum untuk menemukan nilai dalam sebuah koleksi. Tabel di bawah ini menyoroti perbedaan keduanya:

Singkatnya, pencarian biner jauh lebih cepat pada data besar yang sudah diurutkan, sedangkan pencarian linier lebih sederhana dan merupakan satu-satunya pilihan ketika data tidak diurutkan.

Pertanyaan Umum Demo Slot