Algoritma pencarian adalah metode untuk menemukan elemen tertentu dalam suatu struktur data, seperti array atau daftar. Dalam bab ini, kita akan membahas dua algoritma pencarian dasar: pencarian linear dan pencarian biner. Kedua algoritma ini penting karena mereka merupakan dasar dari banyak algoritma pencarian yang lebih kompleks.
3.1 Pencarian Linear
Pencarian linear adalah metode pencarian yang paling sederhana. Algoritma ini memeriksa setiap elemen dalam struktur data secara berurutan hingga elemen yang dicari ditemukan atau hingga akhir struktur data tercapai.
Kelebihan dan Kekurangan Pencarian Linear
- Kelebihan: Sederhana dan mudah diimplementasikan. Tidak memerlukan data terurut.
- Kekurangan: Kurang efisien untuk dataset yang besar karena waktu pencarian yang sebanding dengan ukuran dataset.
Contoh Implementasi Pencarian Linear dalam Python
def pencarian_linear(arr, x):
for i in range(len(arr)):
if arr[i] == x:
return i
return -1
# Contoh penggunaan
arr = [2, 4, 0, 1, 9]
x = 1
result = pencarian_linear(arr, x)
print(f'Elemen ditemukan pada indeks: {result}') # Output: Elemen ditemukan pada indeks: 3
Dalam contoh ini, algoritma memeriksa setiap elemen dalam array arr untuk mencari nilai x. Jika ditemukan, algoritma mengembalikan indeks elemen tersebut; jika tidak, mengembalikan -1.
3.2 Pencarian Biner
Pencarian biner adalah metode pencarian yang lebih efisien dibandingkan pencarian linear, tetapi memerlukan data yang telah terurut. Algoritma ini bekerja dengan membagi dua struktur data dan membandingkan elemen tengah dengan elemen yang dicari. Proses ini diulangi pada setengah yang relevan hingga elemen ditemukan atau interval pencarian kosong.
Kelebihan dan Kekurangan Pencarian Biner
- Kelebihan: Lebih cepat dibandingkan pencarian linear untuk dataset besar karena waktu pencarian yang logaritmik.
- Kekurangan: Memerlukan data terurut, sehingga ada overhead tambahan untuk mengurutkan data jika belum terurut.
Contoh Implementasi Pencarian Biner dalam Python
def pencarian_biner(arr, x):
low = 0
high = len(arr) - 1
while low <= high:
mid = (high + low) // 2
if arr[mid] < x:
low = mid + 1
elif arr[mid] > x:
high = mid - 1
else:
return mid
return -1
# Contoh penggunaan
arr = [1, 2, 3, 4, 5]
x = 4
result = pencarian_biner(arr, x)
print(f'Elemen ditemukan pada indeks: {result}') # Output: Elemen ditemukan pada indeks: 3
Di sini, algoritma mencari nilai x dalam array arr yang telah terurut. Algoritma ini mengurangi ukuran interval pencarian setengah demi setengah hingga elemen ditemukan atau interval kosong.
3.3 Penerapan Pencarian dalam Python
Mari kita lihat beberapa penerapan praktis dari algoritma pencarian dalam situasi kehidupan nyata.
Penerapan 1: Mencari Nama dalam Daftar
def cari_nama(daftar_nama, nama):
return pencarian_linear(daftar_nama, nama)
# Contoh penggunaan
daftar_nama = ["Alice", "Bob", "Charlie", "Diana"]
nama = "Charlie"
indeks = cari_nama(daftar_nama, nama)
print(f'{nama} ditemukan pada indeks: {indeks}') # Output: Charlie ditemukan pada indeks: 2
Penerapan 2: Mencari Angka dalam Daftar Terurut
def cari_angka_terurut(daftar_angka, angka):
return pencarian_biner(daftar_angka, angka)
# Contoh penggunaan
daftar_angka = [10, 20, 30, 40, 50]
angka = 30
indeks = cari_angka_terurut(daftar_angka, angka)
print(f'{angka} ditemukan pada indeks: {indeks}') # Output: 30 ditemukan pada indeks: 2
Kesimpulan Bab 3
Pada bab ini, kita telah membahas dua algoritma pencarian dasar: pencarian linear dan pencarian biner. Pencarian linear cocok untuk dataset kecil dan tidak terurut, sementara pencarian biner lebih efisien untuk dataset besar yang telah terurut. Memahami kedua algoritma ini adalah dasar yang penting untuk mempelajari algoritma pencarian yang lebih kompleks dan aplikasi praktis dalam pemrograman.
Di bab selanjutnya, kita akan mengeksplorasi algoritma pengurutan, yang sering digunakan bersama dengan algoritma pencarian untuk memproses data secara efisien.