Searching Dalam Python
Hai semuanya! balik lagi sama aku Asfa. Pada pertemuan Praktikum Struktur Data kali ini aku mempelajari apa aja tentang searching di python. Kalau kalian penasaran yuk ikut belajar juga!
Seperti namanya ini merupakan algoritma yang digunakan untuk melakukan pencarian untuk menemukan elemen tertentu dalam kumpulan data. Disini kita akan mempelajari 2 jenis metode pencarian yang paling umum dan sering digunakan yaitu:
- Linear searching (skuensial): Menelusuri semua elemen secara berurutan.
- Binarry searching (inerval): Menelusuri dengan cara membagi kumpulan data menjadi beberapa interval.
Untuk penerapanya pada python sebagai berikut.
Linear Search
Linear Search adalah metode pencarian berurutan yang dimulai dari satu titik dan melewati setiap elemen dari daftar sampai elemen yang dicari ditemukan. Pada Linear Search, setiap elemen dianggap sebagai kemungkinan pencocokan dengan kunci pencarian, dan diperiksa untuk kesesuaiannya. Penerapannya,
# membuat fungsi linear search
def linear_search(arr, N, x):
for i in range(0, N):
if (arr[i] == x):
return i
return -1
# menjalankan kode
arr = [20, 10, 30, 50, 40]
x = 10
N = len(arr)
hasil = linear_search(arr, N, x)
if(hasil == -1):
print("Element yang dicari tidak ada di dalam array")
else:
print(f"Element yang dicari berada di indeks ke -{hasil}")
Analisis: Kondisi untuk melakukan pengecekkan dilakukan saat di perulangan for , dengan adanya if statement untukmelakukan pengecekkan apakah sama dengan nilai kuncinya.
Metode pencarian ini sangat disarankan jika menangani dataset yang kecil, karena tidak memerlukan memori tambahan. Namun, saat menghadapi dataset yang besar metode pencarian ini menjadi sangat lama karena harus melakukan pencocokan elemen satu per satu, terutama saat target berada di urutan terakhir sebuah dataset.
Binnary Search
Selanjutnya adalah binnary search, yaitu adalah metode pencarian yang dilakukan dengan membagi array menjadi interval interval. Namun terdapat satu syarat yang harus terpenuhi juga, yaitu kumpulan data tersebut harus sudah terurut dalam kompleksitas waktu O(log N).
Pembagian menjadi interval nya dilakukan dengan membagi menggunakan 3 batasan yaitu left , mid , right. Sehingga mendapati 2 bagian interval.
Alur pencariannya yaitu dengan membandingkan nilai kunci dengan nilai mid nya. Jika nilai kunci lebih kecil dari nilai mid nya maka batas right nya akan menjadi indeksmid + 1, begitu juga jika nilai kunci lebih besar dari nilai mid nya, maka batas kirinya menjadi indeks mid + 1.
Untuk binnary search dapat di terapkan dengan dua cara sebagai berikut.
A. Binnary search iteratif
def binnary_search(arr, l, r, x):
while l <= r:
mid = l + (r-l) // 2
if arr[mid] == x:
return mid
elif arr[mid] < x:
l = mid + 1
else:
r = mid + 1
return -1
if __name__ == "__main__":
arrei = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]
x = 72
res = binnary_search(arrei, 0, len(arrei)-1, x)
if(res != -1):
print(f"Element yang dicari berada di indeks ke -{res}")
else:
print("Element yang dicari tidak ada di dalam array")
B. Binnary search rekrusif
def rekrusif_binnary(arr, l, r, x):
if r >= l:
mid = l + (r-l) // 2
if arr[mid] == x:
return mid
elif arr[mid] > x:
return rekrusif_binnary(arr, l, mid-1, x)
else:
return rekrusif_binnary(arr, mid+1, r, x)
else:
return -1
if __name__ == "__main__":
arrbin = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]
x = 12
result = rekrusif_binnary(arrbin, 0, len(arrbin)-1, x)
if(result != -1):
print(f"Element yang dicari berada di indeks ke -{result}")
else:
print("Element yang dicari tidak ada di dalam array")
Analisis: Untuk kedua metode tersebut dibedakan bagaimana cara membagi dan menelusuri pada elemennya.
Untuk metode iteratif menggunakan while loop yang dibatasi saat right nya ≥ dari left nyauntuk menelusuri tiap elemennya nya dan mengubah posisi left dan right nya yang disipan kesebuah variabel yang akan terus berubah sampai mid == key.
Get aasfadani’s stories in your inbox
Join Medium for free to get updates from this writer.
Sedangkan untuk metode rekrusiif tidak menggunakan while loop, tapi langsung dengan if statement. Dan untuk merubah posisi left dan right nya dengan menjalankan fungsi di dalam fungsi nya. Dimana merubah parameter nya.
Jump Search
Metode pencarian untuk array yang sudah terurut. Secara sederhana samadengan metode pencarian linier namun lebih sedikit mencocokkan karena melewati beberapa elemen. Penerapan,
def jump_search(arr, x, n):
import math
step = math.sqrt(n)
prev = 0
while arr[int(min(step, n)-1)] < x:
prev = step
step += math.sqrt(n)
if prev >= n:
return -1
while arr[int(prev)] < x:
prev += 1
if prev == min(step, n):
return -1
if arr[int(prev)] == x:
return prev
return -1
if __name__ == "__main__":
arrj = [0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610]
x = 55
n = len(arrj)
index = jump_search(arrj, x, n)
print(f"angka {x} berada di indeks ke-{"%.0f"%index}")
Studi Kasus 1
Mencari nilai min dan max pada array.
class nilai:
def __init__(self):
self.min = 0
self.max = 0
def CariMinMax(arr: list, n: int):
minmax = nilai()
if n == 1:
minmax.min = arr[0]
minmax.max = arr[0]
return minmax
if arr[0] > arr[1]:
minmax.min = arr[1]
minmax.max = arr[0]
else:
minmax.min = arr[0]
minmax.max = arr[1]
for i in range(2, n):
if arr[i] > minmax.max:
minmax.max = arr[i]
elif arr[i] < minmax.min:
minmax.min = arr[i]
return minmax
if __name__ == "__main__":
import random
arr = []
for i in range(0, 10):
i = random.randint(50, 100)
arr.append(i)
minmax = CariMinMax(arr, len(arr))
print(f"""
Array:
{arr}
Nilai min nya: {minmax.min}
Nilai max nya: {minmax.max}
""")
Analisis: Pencarian nilai min dan max dari sebuah array ini menggunakan linear search. Karena alurnya menelusuri dan membandingkan nilai yang sebelumnya sudah di simpan ke node (min/max)nya satu persatu dan mengubah nilai yang sudah tersimpan jika pada iterasi terbaru nilai nya lebih kecil.
Studi Kasus 2
Mencari nilai terduplikasi atau nilai kosong pada sebuah array terurut.
def MissingDuplikat(arr: list):
n = len(arr)
temp = [0] * n
angka_hilang = -1
angka_dobel = -1
for i in range(n):
temp[arr[i]-1] += 1
if temp[arr[i]-1] > 1:
angka_dobel = arr[i]
for i in range(n):
if temp[i] == 0:
angka_hilang = i + 1
break
return angka_hilang, angka_dobel
if __name__ == "__main__":
import random
arr = [0,2,3,2]
print(arr)
nilai = MissingDuplikat(arr=arr)
print(f"\nAngka yang hilang\t: {nilai[0]}")
print(f"Angka yang dobel\t: {nilai[1]}")
Analisis: Pada metode pencarian nilai hilang dan terduplikat ini juga menggunakan metode linear search juga, dengan mencocokkan nilai.
Studi Kasus 3
Mencari pasangan nilai yang hasil jumlahnya sama dengan nilai kunci
def cari_pasangan(arr: list, key: int):
key = key
for i in arr:
for j in arr:
hasil = i + j
if hasil == key:
return print(f"Terdapat angka pasangan {i,j} dengan jumlah = {hasil}")
return print(f"Tidak ada pasangan angka yang jumlah nya sama dengan key, key = {key}")
if __name__ == "__main__":
arr = [11, 15, 6, 8, 9, 10]
x = 16
y = 55
print(f"{arr}\nKunci: {x}\n")
hasil = cari_pasangan(arr, x)
print(f"\n{arr}\nKunci: {y}\n")
hasil = cari_pasangan(arr, y)
Analisis: Pada studi kasus ke 3 pun penyelesaiannya juga dapat di lakukan dengan linear search.
Penerapan di kehidupan sehari hari
Penerapan dari linear search di kehidupan sehari hari dapat kita jumpai di notepad atau alat pencatatan lain. Fitur untuk mencari kata ataupun huruf menggunakan metode linear search. Sistem akan menelusuri satu persatu huruf atau kata yang ada pada catatan yang dicarinya.
Demikian contoh penerapan stack di kehidupan sehari hari.
Referensi dan Lampiran
Sebagai bagian dari transparansi dan dokumentasi teknis, seluruh kode sumber yang digunakan dalam praktikum ini telah diunggah ke repositori GitHub. Hal ini juga bertujuan untuk memudahkan pengelolaan versi (version control) di masa mendatang.
- GitHub Repositori: https://github.com/asfadani/asfadani_kuliah.git
- File IPYNB: Praktikum 5 Struktur Data — Searching pada Python
- Referensi: Sumanda Ika Novichasari. Searching Dalam Python. Universitas Tidar Magelang.
Disusun Oleh
Muhammad Fauza Asfadani (2505060011)
TIF25/R-01
