Linear & Binary Search
Pencarian Bilangan/Searching¶
Misalkan diberikan sebuah array yang berisi bilangan bulat secara acak, $A$.
Untuk melakukan pencarian bilangan $x$ pada $A$, kita bandingkan satu per satu apakah $A[1]=x$, apakah $A[2]=x$, dst sampai $A[n]=x$.
Proses pencarian ini dinamakan Linear Search
Misalkan diberikan sebuah array yang berisi bilangan bulat secara terurut, A.
Untuk mencari bilangan $x$ pada $A$, bisa digunakan Linear Search, tetapi apakah cara pencarian ini paling baik?.
Binary Search
Binary search adalah salah satu algoritma yang populer untuk melakukan pencarian elemen pada array terurut $A$ berukuran $n$.
Idenya adalah cari cek apakah $x$ sama dengan elemen yang ada di tengah Array.
- Jika elemen tengah sama dengan $x$, selesai
- Jika elemen tengah lebih kecil dari yang dicari,
- Bagi 2 array ini, fokus ke bagian kanan. Bandingkan $x$ dengan elemen tengah dari array yang sudah dibagi 2.
- Jika elemen tengah lebih besar dari yang dicari,
- Bagi 2 array ini, fokus ke bagian kiri. Bandingkan $x$ dengan elemen tengah dari array yang sudah dibagi 2.
- Proses di atas dilakukan berulang-ulang sampai mendapat kesimpulan apakah $x$ ada di dalam array $A$ atau tidak.
Untuk array berukuran lebih dari 6, banyak iterasi dari Algoritma ini adalah tidak lebih dari $n/2$
In [1]:
def bubble_sort(A):
#input A : Array of float
#ouput A : ordered Array of float
for j in range(len(A)-1):
for i in range(0,len(A)-1-j):
if A[i]>A[i+1]:
temp=A[i]
A[i]=A[i+1]
A[i+1]=temp
return A
In [2]:
import random
random.seed(2)
A = [random.randrange(1, 300, 1) for i in range(100)]
bubble_sort(A)
print ("Random Array of Integer : ", A)
find=random.randrange(1,300)
print(find)
Random Array of Integer : [5, 13, 15, 19, 19, 26, 29, 31, 39, 44, 47, 55, 55, 70, 70, 82, 83, 85, 86, 87, 89, 91, 91, 94, 98, 107, 109, 114, 117, 119, 121, 126, 128, 129, 137, 138, 138, 140, 143, 156, 158, 159, 160, 164, 167, 167, 175, 180, 182, 182, 185, 185, 186, 187, 187, 188, 191, 195, 202, 205, 209, 213, 217, 221, 228, 229, 229, 233, 234, 237, 237, 239, 246, 250, 251, 251, 256, 257, 258, 259, 260, 261, 262, 262, 263, 264, 264, 266, 268, 269, 270, 272, 279, 286, 287, 287, 288, 291, 295, 298] 108
In [3]:
find=100 #bilangan yang ingin dicari
In [4]:
#Linear Search, dicari dari depan
ketemu=False
i=0
while i<len(A) and A[i]<=find and ketemu==False:
print("Apakah",find,"sama dengan nilai A[",i,"]=",A[i])
if find == A[i]:
ketemu=True
print(find,"berada pada array A indeks ke",i)
i=i+1
if ketemu==False:
print(find,"tidak berada pada array A, karena A[",i,"]=",A[i])
print("Banyak iterasi pencarian",i)
Apakah 100 sama dengan nilai A[ 0 ]= 5 Apakah 100 sama dengan nilai A[ 1 ]= 13 Apakah 100 sama dengan nilai A[ 2 ]= 15 Apakah 100 sama dengan nilai A[ 3 ]= 19 Apakah 100 sama dengan nilai A[ 4 ]= 19 Apakah 100 sama dengan nilai A[ 5 ]= 26 Apakah 100 sama dengan nilai A[ 6 ]= 29 Apakah 100 sama dengan nilai A[ 7 ]= 31 Apakah 100 sama dengan nilai A[ 8 ]= 39 Apakah 100 sama dengan nilai A[ 9 ]= 44 Apakah 100 sama dengan nilai A[ 10 ]= 47 Apakah 100 sama dengan nilai A[ 11 ]= 55 Apakah 100 sama dengan nilai A[ 12 ]= 55 Apakah 100 sama dengan nilai A[ 13 ]= 70 Apakah 100 sama dengan nilai A[ 14 ]= 70 Apakah 100 sama dengan nilai A[ 15 ]= 82 Apakah 100 sama dengan nilai A[ 16 ]= 83 Apakah 100 sama dengan nilai A[ 17 ]= 85 Apakah 100 sama dengan nilai A[ 18 ]= 86 Apakah 100 sama dengan nilai A[ 19 ]= 87 Apakah 100 sama dengan nilai A[ 20 ]= 89 Apakah 100 sama dengan nilai A[ 21 ]= 91 Apakah 100 sama dengan nilai A[ 22 ]= 91 Apakah 100 sama dengan nilai A[ 23 ]= 94 Apakah 100 sama dengan nilai A[ 24 ]= 98 100 tidak berada pada array A, karena A[ 25 ]= 107 Banyak iterasi pencarian 25
In [5]:
#Binary Search
import math
step=0
lb=0
ub=len(A)
ketemu=False
print("Diberikan Array A=",A)
print("Dengan ukuran A=",len(A))
while lb<ub and ketemu==False:
mp=math.ceil((ub+lb)/2)
print("Apakah",find,"sama dengan nilai A[",mp,"]=",A[mp])
if (find==A[mp]):
print(find,"berada pada array A indeks ke",mp)
ketemu=True
elif (find<A[mp]):
ub=mp-1
else:
lb=mp+1
if ketemu==False:
print(find,"tidak berada pada array A")
Diberikan Array A= [5, 13, 15, 19, 19, 26, 29, 31, 39, 44, 47, 55, 55, 70, 70, 82, 83, 85, 86, 87, 89, 91, 91, 94, 98, 107, 109, 114, 117, 119, 121, 126, 128, 129, 137, 138, 138, 140, 143, 156, 158, 159, 160, 164, 167, 167, 175, 180, 182, 182, 185, 185, 186, 187, 187, 188, 191, 195, 202, 205, 209, 213, 217, 221, 228, 229, 229, 233, 234, 237, 237, 239, 246, 250, 251, 251, 256, 257, 258, 259, 260, 261, 262, 262, 263, 264, 264, 266, 268, 269, 270, 272, 279, 286, 287, 287, 288, 291, 295, 298] Dengan ukuran A= 100 Apakah 100 sama dengan nilai A[ 50 ]= 185 Apakah 100 sama dengan nilai A[ 25 ]= 107 Apakah 100 sama dengan nilai A[ 12 ]= 55 Apakah 100 sama dengan nilai A[ 19 ]= 87 Apakah 100 sama dengan nilai A[ 22 ]= 91 Apakah 100 sama dengan nilai A[ 24 ]= 98 100 tidak berada pada array A
Apakah algoritma Binary Search selalu lebih cepat dari Linear Search?
Silahkan simulasikan dan dipikirkan :)
Comments
Post a Comment