Linear Search dan Binary Search

 Kali ini kita akan membahas Linear Search dan Binary Search serta contoh program sederhana dari kedua metode tersebut.

Linear Search

Atau bisa dikenal juga sebagai Sequential Search adalah metode pencarian yang paling sederhama. Algoritma ini bekerja dengan cara memeriksa setiap elemen dalam daftar secara berurutan, mulai dari elemen pertama hingga elemen terakhir, sampai seluruh daftar telah diperiksa hingga elemen yang ingin dicari telah didapatkan atau tidak ada di dalam daftar.

Cara Kerjanya Linear Search adalah sebagai berikut:

1. Daftar yang ingin dicari sudah tersusun berurutan.

2. Menentukan titik tengah/pivot dari daftar.

3. Membandingkan nilai yang dicari dengan elemen di titik tengah.

    a. Jika cocok, pencarian berhasil

    b. Jika nilai yang dicari lebih kecil dari elemen tengah, abaikan setengah bagian kanan (elemen            lebih besar dan elemen tengah) dan mengulangi pencarian pada setengah bagian kiri.

    c. Jika nilai yang dicari lebih besar dari elemen tengah, abaikan setengah bagian kiri (elemen lebih         kecil dan elemen tengah) dan mengulangi pencarian pada setengah bagian kanan.

4. Mengulangi proses pencarian hingga nilai ditemukan atau sisa sub-daftar menjadi kosong.

Kelebihan dan Kekuranga Linear Search

Kelebihan: Sangat mudah di implementasikan. Bekerja pada daftar yanng tidak perlu diurutkan.

Kekurangan: Sangat lambat untuk daftar yang besar karena harus memeriksa setiap elemen.

Binary Search

Binary Search adalah algoritma pencarian yang jauh lebih efisien dibandingkan Linear Search, tetapi hanya dapat bekerja pada daftar yang sudah diurutkan secara menaik atau menurun. Algoritma ini bekerja dengan membagi daftar menjadi dua bagian pada tiap langkah.

Cara Kerja Binary Search:

1. Daftar yang ingin digunakan sudah dalam keadaan terurut.

2. Menentukan titik tengah/pivot dari daftar.

3. Membandingkan nilai yang dicari dengan elemen di titik tengah.

    a. Jika cocok, pencarian berhasil.

    b. Jika nilai yang dicari lebih kecil dari elemen tengah, abaikan setengah bagian kanan (elemen            lebih besar dan elemen tengah) dan mengulangi pencarian pada setengah bagian kiri.

    c. Jika nilai yang dicari lebih besar dari elemen tengah, abaikan setengah bagian kiri (elemen lebih         kecil dan elemen tengah) dan mengulangi pencarian pada setengah bagian kanan.

4. Mengulangi proses pencarian hingga nilai ditemukan atau sisa sub-daftar menjadi kosong.

Kelebihan dan Kekurangan Binary Search

Kelebihan: Sangat cepat dan efisien, terutama untuk daftar yang besar.

Kekurangan: Memerlukan daftar yang telah diurutkan terlebih dahulu. Proses pengurutan itu sendiri dapat memakan waktu yang banyak.

Kesimpulan

Dari kedua metode yang disebutkan, Linear Search lebih unggul di implementasikan pada daftar data yang relatif kecil dan tidak berurutan, tetapi dengan kecepatan yang lambat.

Sedangkan Binary Search lebih unggul dalam kecepatan dan dapat di implementasikan pada daftar yang relatif besar, namun daftar tersebut wajib diurutkan terlebih dahulu dan proses pengurutannya juga akan memakan banyak waktu

Contoh Program Sederhana

Linear Search

#program linear search

#data

angka = [3, 9, 11, 12, 15, 17, 23, 31, 35]

dicari = 23

#linear search

found = False

for i in range(len(angka)):

  if angka[i] == dicari:

    print(f"Angka {dicari} ditemukan pada indeks ke-{i}")

    found = True

    break

if not found:

  print(f"Angka {dicari} tidak ditemukan")

Output:

Angka 23 ditemukan pada indeks ke-6

Binary Search

#program binary search

#data

angka = [3, 9, 11, 12, 15, 17, 23, 31, 35]

dicari = 23

#binary search

low = 0

high = len(angka) - 1

found = False

while low <= high:

  mid = (low + high) // 2

  if angka[mid] == dicari:

    print(f"Angka {dicari} ditemukan pada indeks ke-{mid}")

    found = True

    break

  elif angka[mid] < dicari:

    low = mid + 1

  else:

    high = mid - 1

if not found:

  print(f"Angka {dicari} tidak ditemukan")

Output:

Angka 23 ditemukan pada indeks ke-6