Searching atau pencarian adalah salah satu konsep yang
fundamental dalam dunia pemprograman. Layaknya di dunia nyata, kita
tidak hanya memproses/mengolah data saja, melainkan menyimpan/merekam
data di suatu wadah. Saat kita membutuhkan data tersebut, kita melakukan
pencarian. Metode pencarian yang paling dasar adalah
linear dan
binary. Gimana itu? Mari baca ide dasarnya dulu lalu kita implementasikan di kodingan kita :D
Algoritma ini mencari data yang kita inginkan satu-per-satu dari awal hingga data terakhir tanpa adanya
jump
atau melewati suatu data tertentu. Pencarian inilah yang sangat
intuitif, manusia pada umumnya menggunakan metode pencarian ini. Yang
menjadi keunggulan metode pencarian ini adalah karena algoritma ini
mengecek data satu-per-satu, maka hasilnya terjamin/pasti ada atau tidak
ada. Mari kita lihat kodingannya :
angka
=
[
43
,
2
,
99
,
0
,
37
,
1
,
4
,
5
,
6
,
33
]
def
cari(N):
for
i
in
angka:
if
(i
=
=
N):
return
True
return
False
print
(cari(
5
))
print
(cari(
9
))
Jauh berbeda dengan
linear search, algo ini menggukan
jumps. Ide dari dari algo ini adalah mencari sebuah data dari kumpulan data yang
TERURUT
dengan cara membagi kumpulan data tersebut menjadi 2 bagian yang sama
dan melihat data yang ada di tengah kumpulan data tersebut serta
membandingkan dengan data yang kita cari. Jadi,
binary search
melihat data yang berada di tengah dulu, bukan di awal. Asumsikan data
yang kita miliki sudah terurut ascending. Jika data yang berada di
tengah itu lebih besar daripada yang kita cari, maka kita hanya akan
melihat data pertama hingga data ke-ten
gah-1.
Begitu pula apabila data tengah lebih kecil, maka kita akan melihat
data ke-tengah+1 hingga terakhir. Mari lihat kodingannya:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
|
angka = [ 43 , 2 , 99 , 0 , 37 , 1 , 4 , 5 , 6 , 33 ]
angka.sort()
def cari(N):
kiri = 0
kanan = len (angka)
while (kiri< = kanan):
tengah = (kiri + kanan) / / 2
if (angka[tengah] = = N): return True
elif (angka[tengah]>N): kanan = tengah - 1
else : kiri = tengah + 1
return False
print (cari( 5 ))
print (cari( 9 ))
print (cari( 99 ))
|
Kalo masih bingung, ini ada
gif biar lebih paham :D
|
source: www.penjee.com | |