Algoritma Pencarian (Searching Algorithm) Pada Bahasa Program Python

Tutorialspoint menjelaskan  pencarian adalah kebutuhan dasar ketika Anda menyimpan data dalam berbagai struktur data. Pendekatan yang paling sederhana adalah dengan memeriksa setiap elemen dalam struktur data dan mencocokkannya dengan nilai yang Anda cari. Ini dikenal sebagai Pencarian Linear. Meskipun tidak efisien dan jarang digunakan, membuat program untuk pencarian linear memberi gambaran tentang bagaimana kita dapat mengimplementasikan beberapa algoritma pencarian yang lebih canggih.

GeeksForGeeks menjelaskan bahwa Algoritma pencarian merupakan alat penting dalam ilmu komputer yang digunakan untuk menemukan item tertentu dalam kumpulan data. Algoritma ini dirancang untuk menavigasi secara efisien melalui struktur data guna menemukan informasi yang diinginkan, sehingga menjadikannya penting dalam berbagai aplikasi seperti basis data, mesin pencari web , dan banyak lagi.

Pencarian Linear

Pencarian linear adalah algoritma pencarian yang paling sederhana. Algoritma ini memeriksa setiap elemen dalam daftar secara berurutan hingga menemukan nilai yang dicari.

Langkah-langkah:

1. Mulai dari elemen pertama dalam daftar.
2. Bandingkan setiap elemen dalam daftar dengan nilai target.
3. Jika elemen cocok dengan nilai target, kembalikan indeksnya.
4. Jika nilai target tidak ditemukan setelah memeriksa seluruh daftar, kembalikan -1.

Implementasi Linear Search dalam Python:

def linear_search(arr, target):     """     Melakukan pencarian linear untuk menemukan nilai target dalam daftar yang diberikan.     Parameter:         arr (list): Daftar yang akan dicari.         target: Nilai yang dicari.     Mengembalikan:         int: Indeks nilai target jika ditemukan, jika tidak ditemukan mengembalikan -1.     """     for i in range(len(arr)):         if arr[i] == target:             return i     return -1 # Contoh penggunaan: arr = [2, 3, 4, 10, 40] target = 10 result = linear_search(arr, target) if result != -1:     print(f"Pencarian Linear: Elemen ditemukan pada indeks {result}") else:     print("Pencarian Linear: Elemen tidak ditemukan")

Analisis Kompleksitas Waktu

Freecodecamp menjelaskan analisis kompleksitas waktu untuk pencarian linear adalaha sebagai berikut,

Kasus Terbaik terjadi ketika elemen target adalah elemen pertama dari array. Jumlah perbandingan dalam hal ini adalah 1. Jadi, kompleksitas waktu adalah O(1).

Kasus Rata-rata: Secara rata-rata, elemen target akan berada di sekitar tengah array. Jumlah perbandingan, dalam hal ini, adalah N/2. Jadi, kompleksitas waktu akan menjadi O(N) (konstanta diabaikan).

Kasus Terburuk terjadi ketika elemen target adalah elemen terakhir dalam array atau tidak ada dalam array sama sekali. Dalam hal ini, kita harus menelusuri seluruh array, sehingga jumlah perbandingannya adalah N. Jadi, kompleksitas waktu akan menjadi O(N).

Pencarian Biner 

Pencarian biner adalah algoritma pencarian yang lebih efisien dan cocok untuk daftar yang sudah terurut. Algoritma ini secara berulang membagi interval pencarian menjadi dua hingga nilai target ditemukan.

Langkah-langkah:

1. Mulailah dengan seluruh daftar yang terurut.
2. Hitung elemen tengah dari daftar.
3. Jika elemen tengah sama dengan nilai target, kembalikan indeksnya.
4. Jika elemen tengah lebih kecil dari nilai target, cari di bagian kanan daftar.
5. Jika elemen tengah lebih besar dari nilai target, cari di bagian kiri daftar.
6. Ulangi langkah 2-5 hingga nilai target ditemukan atau interval pencarian kosong.

Implementasi Pencarian Biner dalam Python (Rekursif):

Berikut terjemahan komentar dalam bahasa Indonesia: def binary_search(arr, target, low, high):     """     Melakukan pencarian biner secara rekursif untuk menemukan nilai target dalam daftar yang terurut.     Parameter:         arr (list): Daftar yang terurut untuk dicari.         target: Nilai yang dicari.         low (int): Indeks bawah dari interval pencarian.         high (int): Indeks atas dari interval pencarian.     Mengembalikan:         int: Indeks nilai target jika ditemukan, jika tidak ditemukan mengembalikan -1.     """     if low <= high:         mid = (low + high) // 2         if arr[mid] == target:             return mid         elif arr[mid] < target:             return binary_search(arr, target, mid + 1, high)         else:             return binary_search(arr, target, low, mid - 1)     else:         return -1 # Contoh penggunaan: arr = [2, 3, 4, 10, 40] target = 10 result = binary_search(sorted(arr), target, 0, len(arr) - 1) if result != -1:     print(f"Pencarian Biner: Elemen ditemukan pada indeks {result}") else:     print("Pencarian Biner: Elemen tidak ditemukan")

Analisis Kompleksitas Waktu

• Kasus Terbaik terjadi ketika elemen target adalah elemen tengah dari array. Jumlah perbandingan dalam hal ini adalah 1. Jadi, kompleksitas waktu adalah O(1).
• Kasus Rata-rata: Secara rata-rata, elemen target akan berada di suatu tempat dalam array. Jadi, kompleksitas waktu akan menjadi O(logN).
• Kasus Terburuk terjadi ketika elemen target tidak ada dalam daftar atau jauh dari elemen tengah. Jadi, kompleksitas waktu akan menjadi O(logN).

Cara Menghitung Kompleksitas Waktu:

Freecodecamp menjelaskan, Misalkan iterasi dalam Binary Search berakhir setelah k iterasi.

Pada setiap iterasi, array dibagi dua. Jadi, misalkan panjang array pada iterasi apapun adalah N.

Pada Iterasi 1,

Panjang array = N
Pada Iterasi 2,

Panjang array = N/2
Pada Iterasi 3,

Panjang array = (N/2)/2 = N/2²
Pada Iterasi k,

Panjang array = N/2ᵏ
Selain itu, kita tahu bahwa setelah k pembagian, panjang array menjadi 1: Panjang array = N/2ᵏ = 1 ⇒ N = 2ᵏ

Jika kita terapkan fungsi log pada kedua sisi: log₂(N) = log₂(2ᵏ) ⇒ log₂(N) = k log₂(2)

Karena (loga(a) = 1)
Maka, ⇒ k = log₂(N)

Jadi, sekarang kita bisa melihat mengapa kompleksitas waktu dari Binary Search adalah log₂(N).

Datacamp menjelaskan diantara penerapan di dunia nyata dari binary search adalah sebagai berikut,

Basis Data
Dalam basis data, pencarian biner sering digunakan untuk dengan cepat menemukan rekaman dalam kolom yang terurut, seperti menemukan pengguna tertentu dalam basis data yang diurutkan berdasarkan ID pengguna. Bayangkan sebuah basis data yang berisi jutaan rekaman. Pencarian linier akan membutuhkan pemindaian setiap rekaman satu per satu, yang bisa memakan waktu cukup lama. Sebaliknya, pencarian biner dapat dengan cepat menemukan rekaman yang diinginkan dengan secara sistematis membagi ruang pencarian, yang secara signifikan mengurangi jumlah perbandingan yang diperlukan.

Ilmu Data
Mencari melalui dataset yang besar dan terurut adalah tugas umum dalam ilmu data. Sebagai contoh, dalam analisis deret waktu, pencarian biner dapat digunakan untuk menemukan stempel waktu tertentu dalam urutan peristiwa yang terurut. Dalam pembelajaran mesin, algoritma pencarian biner dapat digunakan untuk mengoptimalkan hiperparameter dengan menemukan nilai terbaik dalam rentang tertentu.

Grafika Komputer
Dalam grafika komputer, pencarian biner digunakan dalam algoritma di mana presisi dan kecepatan diperlukan. Salah satu contohnya adalah pada teknik pelacakan sinar (ray tracing), yang digunakan untuk mensimulasikan bagaimana cahaya berinteraksi dengan objek. Pencarian biner dapat digunakan untuk dengan cepat menemukan titik-titik perpotongan antara sinar dan permukaan.

Blok Bangunan untuk Algoritma Kompleks
Pencarian biner tidak hanya berguna sendiri; ia juga berfungsi sebagai blok bangunan untuk algoritma dan struktur data yang lebih kompleks. Sebagai contoh, pohon pencarian, seperti pohon pencarian biner (BST), dan pohon seimbang, seperti pohon AVL, didasarkan pada prinsip-prinsip pencarian biner. Struktur-struktur ini memungkinkan pencarian, penyisipan, dan penghapusan yang efisien, menjadikannya berguna ketika data perlu diperbarui dan dicari secara dinamis. Pelajari lebih lanjut tentang pohon-pohon ini dalam Pohon AVL: Panduan Lengkap dengan Implementasi Python.

Pencarian Interpolasi

Interpolation search adalah versi yang lebih baik dari pencarian biner, khususnya cocok untuk array besar yang terdistribusi secara merata. Algoritma ini menghitung posisi yang mungkin dari nilai target berdasarkan nilai kunci dan rentang ruang pencarian.

Tutorialspoint juga menambahkan, Algoritma pencarian ini bekerja dengan memeriksa posisi probe dari nilai yang dibutuhkan. Agar algoritma ini dapat berfungsi dengan baik, koleksi data harus dalam bentuk yang terurut dan terdistribusi secara merata. Awalnya, posisi probe adalah posisi dari item yang paling tengah dalam koleksi. Jika terjadi kecocokan, maka indeks item tersebut dikembalikan. Jika item tengah lebih besar dari item yang dicari, maka posisi probe dihitung kembali pada sub-array di sebelah kanan item tengah. Sebaliknya, jika item tengah lebih kecil dari item yang dicari, maka pencarian dilakukan di sub-array sebelah kiri item tengah. Proses ini berlanjut pada sub-array hingga ukuran sub-array berkurang menjadi nol.

Langkah-langkah:

1. Hitung posisi yang mungkin dari nilai target menggunakan rumus interpolasi.
2. Bandingkan nilai target dengan elemen pada posisi yang dihitung.
3. Jika elemen cocok dengan nilai target, kembalikan indeksnya.
4. Jika elemen lebih kecil dari nilai target, cari di bagian kanan daftar.
5. Jika elemen lebih besar dari nilai target, cari di bagian kiri daftar.
6. Ulangi langkah 1-5 hingga nilai target ditemukan atau interval pencarian kosong.

Implementasi Interpolation Search dalam Python:

Berikut adalah terjemahan komentar dalam kode Python tersebut: import math def interpolation_search(arr, target):     """     Melakukan pencarian interpolasi untuk menemukan nilai target dalam daftar yang terurut.     Parameter:         arr (list): Daftar yang terurut untuk dicari.         target: Nilai yang dicari.     Mengembalikan:         int: Indeks nilai target jika ditemukan, jika tidak ditemukan mengembalikan -1.     """     low = 0     high = len(arr) - 1     while low <= high and target >= arr[low] and target <= arr[high]:         pos = low + ((high - low) // (arr[high] - arr[low])) * (target - arr[low])         if arr[pos] == target:             return pos         elif arr[pos] < target:             low = pos + 1         else:             high = pos - 1     return -1 # Contoh penggunaan: arr = [2, 3, 4, 10, 40] target = 10 result = interpolation_search(sorted(arr), target) if result != -1:     print(f"Interpolation Search: Elemen ditemukan pada indeks {result}") else:     print("Interpolation Search: Elemen tidak ditemukan")

4. Jump Search
Jump search adalah algoritma pencarian lain yang cocok untuk array yang terurut. Algoritma ini melompat maju dengan jumlah langkah tetap dan kemudian melakukan pencarian linier dalam rentang yang lebih kecil.

Langkah-langkah:

1. Tentukan ukuran blok untuk melompat maju.
2. Lompat maju sesuai ukuran blok sampai nilai target lebih besar dari elemen terakhir dalam blok saat ini.
3. Lakukan pencarian linier dalam blok saat ini untuk menemukan nilai target.
4. Jika nilai target ditemukan, kembalikan indeksnya.
5. Jika nilai target tidak ditemukan setelah melalui semua blok, kembalikan -1.

Implementasi Jump Search dalam Python:

import math def jump_search(arr, target):     """     Melakukan pencarian lompat untuk menemukan nilai target dalam daftar yang terurut.     Parameter:         arr (list): Daftar yang akan dicari.         target: Nilai yang akan dicari.     Mengembalikan:         int: Indeks dari nilai target jika ditemukan, jika tidak -1.     """     n = len(arr)     step = int(math.sqrt(n))  # Menentukan ukuran langkah berdasarkan akar kuadrat dari panjang daftar     prev = 0  # Indeks elemen sebelumnya     while arr[min(step, n) - 1] < target:  # Melompat maju sampai menemukan elemen yang lebih besar atau sama dengan target         prev = step         step += int(math.sqrt(n))  # Langkah bertambah sesuai ukuran blok         if prev >= n:  # Jika langkah melebihi panjang daftar             return -1     while arr[prev] < target:  # Pencarian linier dalam blok yang lebih kecil         prev += 1         if prev == min(step, n):  # Jika mencapai batas daftar             return -1     if arr[prev] == target:  # Jika elemen yang dicari ditemukan         return prev     return -1  # Jika target tidak ditemukan # Penggunaan contoh: arr = [2, 3, 4, 10, 40] target = 10 result = jump_search(sorted(arr), target) if result != -1:     print(f"Jump Search: Elemen ditemukan pada indeks {result}") else:     print("Jump Search: Elemen tidak ditemukan")

Contoh Algoritma Pencarian Untuk Array yang tidak Terurut

GeeksForGeeks memberikan contoh pencarian untuk array yang tidak terurut dengan algoritma yang kompleksitas waktunya linear, sebagaimana pada contoh kode berikut

Berikut terjemahan komentar dalam kode tersebut: # Implementasi Python3 untuk mencari elemen dalam # array yang tidak terurut menggunakan # jumlah perbandingan minimum # fungsi untuk mencari elemen dalam # jumlah perbandingan minimum def search(arr, n, x):                  # perbandingan pertama         if (arr[n-1] == x) :                 return "Ditemukan"         backup = arr[n-1]         arr[n-1] = x         # tidak ada kondisi terminasi dan         # oleh karena itu tidak ada perbandingan         i = 0         while(i < n) :                                  # ini akan dieksekusi paling banyak n kali                 # dan oleh karena itu paling banyak n perbandingan                 if (arr[i] == x) :                                                  # mengganti arr[n-1] dengan elemen sebenarnya                         # seperti pada 'arr[]' yang asli                         arr[n-1] = backup                         # jika 'x' ditemukan sebelum indeks '(n-1)',                         # maka elemen tersebut ada dalam array                         if (i < n-1):                                 return "Ditemukan"                         # jika tidak ditemukan dalam array                         return "Tidak Ditemukan"                 i = i + 1 # Kode Penggerak arr = [4, 6, 1, 5, 8] n = len(arr) x = 1 print(search(arr, n, x)) # Kode ini disumbangkan oleh rishabh_jain

Keluaran:

Ditemukan

Kompleksitas Waktu: O(n)
Ruang Bantu: O(1)
Jumlah Perbandingan: Maksimal (n+2) perbandingan

Semoga bermanfaat