Mengenal Algoritma Binary Search

https://shorturl.at/nAKOW

Binary search adalah sebuah algoritma pencarian yang digunakan untuk mencari elemen tertentu dalam sebuah array atau daftar yang sudah diurutkan. Algoritma ini bekerja dengan membagi daftar menjadi dua bagian, kemudian memeriksa elemen tengahnya. Jika elemen yang dicari sama dengan elemen tengah ini, pencarian selesai. Jika tidak, algoritma akan menentukan apakah elemen yang dicari lebih besar atau lebih kecil dari elemen tengah, dan kemudian hanya memeriksa salah satu bagian dari daftar yang masih mungkin mengandung elemen yang dicari. Proses ini terus berlanjut hingga elemen yang dicari ditemukan atau daftar habis diperiksa.

Cara Kerja Binary Search

Cara kerja binary search sangat sederhana. Algoritma ini beroperasi pada daftar yang sudah diurutkan. Berikut adalah langkah-langkah utama dalam binary search:

1. Tentukan Rentang Pencarian Awal: Di awal pencarian, kita memiliki seluruh daftar sebagai rentang pencarian. Rentang ini didefinisikan dengan dua indeks, yaitu awal dan akhir, yang mengacu pada elemen pertama dan terakhir dalam daftar.
2. Hitung Elemen Tengah: Temukan indeks tengah di dalam rentang pencarian dengan rumus tengah = (awal + akhir) / 2.
3. Periksa Elemen Tengah: Bandingkan elemen tengah dengan elemen yang ingin Anda cari. Jika elemen tengah sama dengan elemen yang dicari, maka pencarian selesai, dan Anda telah menemukan elemennya.
4. Perkecil Rentang Pencarian: Jika elemen tengah lebih besar dari elemen yang dicari, maka Anda dapat memastikan bahwa elemen yang dicari hanya mungkin ada di sebelah kiri elemen tengah. Oleh karena itu, perkecil rentang pencarian menjadi antara awal dan tengah - 1. Jika elemen tengah lebih kecil, perkecil rentang menjadi antara tengah + 1 dan akhir.
5. Ulangi Langkah 2–4: Ulangi proses ini sampai Anda menemukan elemen yang dicari atau rentang pencarian menjadi kosong.

Algoritma ini terus membagi rentang pencarian menjadi setengah hingga elemen yang dicari ditemukan atau rentang habis. Hal ini menghasilkan kompleksitas waktu O(log n), di mana n adalah jumlah elemen dalam daftar. Ini sangat efisien dibandingkan dengan pencarian linear yang memiliki kompleksitas waktu O(n).

Contoh kasus dengan menggunakan pemrograman python

ilustrasi binary search

Mari kita ilustrasikan penggunaan binary search dengan sebuah contoh. Misalkan kita memiliki kumpulan data berupa [1, 3, 5, 7, 9, 11, 13, 15] dan kita ingin mencari target dengan angka 7.

Dalam binary search, langkah pertama adalah membagi panjang data dengan 2. Panjang data awal adalah 8, kemudian kita bagi 2, yang menghasilkan 4. Sekarang, kita lihat indeks ke-4 dari data, yaitu angka 9.

Selanjutnya, kita bandingkan angka target (7) dengan hasil indeks ke-4 (9). Jika target lebih besar dari 9, maka angka [1, 3, 5, 7, 9] akan dihilangkan dari kumpulan data. Namun, jika target lebih kecil dari 9, maka angka [9, 11, 13, 15] akan dihilangkan.

Proses ini terus berlanjut, dengan data yang tersisa, hingga target menemukan angka yang sama dalam kumpulan data. Binary search memungkinkan kita untuk secara efisien mencari nilai yang diinginkan dalam set data yang besar dengan mengurangi setengah opsi pada setiap langkahnya.

Berikut contoh dengan menggunakan python.

def binary_search(sorted_list, target):
    left = 0
    right = len(sorted_list)

    while left < right:
        middle = (left + right) // 2
        if sorted_list[middle] == target:
            return middle
        elif sorted_list[middle] < target:
            left = middle + 1
        else:
            right = middle

    return None

def main():
    sorted_data = [1, 3, 5, 7, 9, 11, 13, 15]
    target = 7

    index = binary_search(sorted_data, target)
    if index is not None:
        print(f"Elemen {target} ditemukan di indeks {index}.")
    else:
        print(f"Elemen {target} tidak ditemukan dalam daftar.")

if __name__ == "__main__":
    main()

Dalam implementasi Python di atas, fungsi binary_search menerima daftar yang sudah diurutkan dan elemen yang ingin dicari. Kemudian, ia mengembalikan indeks elemen yang dicari jika ditemukan atau None jika tidak ditemukan. Fungsi main digunakan untuk menguji pencarian elemen tertentu dalam contoh daftar yang sudah diurutkan.