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 :)