Algoritma Linear Search dan Binary Search

Pencarian Linier
Pencarian linier atau sering disebut dengan sequential search adalah algoritma pencarian yang sangat sederhana. Dalam jenis pencarian ini, pencarian sekuensial dibuat berdasarkan semua item satu per satu. Setiap item diperiksa dan jika ada kecocokan maka item tertentu dikembalikan, jika tidak pencarian berlanjut sampai akhir pengumpulan data.
Algoritma seperti di bawah ini Linear Search ( Array A, Value x)
Step 1: Set i to 1
Step 2: if i > n then go to step 7
Step 3: if A[i] = x then go to step 6
Step 4: Set i to i + 1
Step 5: Go to Step 2
Step 6: Print Element x Found at index i and go to step 8
Step 7: Print element not found
Step 8: Exit




Pseudocode
procedure linear_search (list, value)
for each item in the list
if match item == value
return the item's location
end if
end for
end procedure


Pencarian Biner
Pencarian biner adalah algoritma pencarian cepat dengan kompleksitas run-time Ο (log n). Algoritma pencarian ini bekerja berdasarkan prinsip membagi dan menaklukkan. Agar algoritma ini bekerja dengan baik, pengumpulan data harus dalam bentuk yang disortir.
Pencarian biner mencari item tertentu dengan membandingkan item paling tengah dari koleksi. Jika terjadi kecocokan, maka indeks item dikembalikan. Jika item tengah lebih besar dari item, item akan dicari di sub-array di sebelah kiri item tengah. Jika tidak, item tersebut dicari di sub-array di sebelah kanan item tengah. Proses ini berlanjut pada sub-array juga sampai ukuran subarray dikurangi menjadi nol.
Pseudocode
Procedure binary_search A ← sorted array
n ← size of array
x ← value to be searched
Set lowerBound = 1
Set upperBound = n
while x not found
if upperBound < lowerBound
EXIT: x does not exists.
set midPoint = lowerBound + ( upperBound - lowerBound ) / 2
if A[midPoint] < x
set lowerBound = midPoint + 1
if A[midPoint] > x
set upperBound = midPoint - 1
if A[midPoint] = x
EXIT: x found at location midPoint
end while
end procedure


pencarian biner cocok digunakan untuk partial kata saat event text_change sedangkan untuk yang binary cocok untuk pencarian dengan kriteria yang spesifik.

Sekian terima kasih

Share :