Algoritma Pencarian Linier dan Pencarian Binary

Pencarian (searching) merupakan suatu pekerjaan yang sering dikerjakan dalam kehidupan sehari – hari. Ada kalanya kita mencari sesuatu dengan tujuan hanya untuk mengetahui apakah data tersebut ada dalam sekumpulan data atau tidak, sementara di lain waktu mungkin kita menginginkan posisi dari data yang dicari tersebut. 

Dalam ilmu komputer terdapat bermacam – macam algoritma untuk metoda pencarian (searching). Beberapa metoda pencarian yang pernah dipelajari adalah metoda pencarian linier (Linear / Sequential Search), pencarian biner (Binary Search) dan pencarian interpolasi (Interpolation Search). Masing – masing algoritma memiliki prasyarat dan cara serta waktu pelaksanaan yang berbeda. Pemilihan atas metoda pencarian dilakukan berdasarkan keadaan dan keinginan pengguna metoda yang biasanya tergantung pada jumlah data, jenis data dan struktur data yang digunakan.

PENCARIAN LINIER

Pencarian Linier atau Pencarian Sekuensial (Bah.Ingg: Linear Search atau Sequential Search) adalah pencarian data secara linier (garis lurus), artinya adalah pencarian dilakukan secara teratur (secara sekuensial) dari awal sampai akhir data (atau bisa juga dari akhir ke awal data). Berikut adalah 2 fakta penting tentang pencarian linier:

·         Hanya bagus untuk dipakai pada data yang acak/tak terurut (unsorted)

·         Kompleksitasnya adalah O(n)

Berikut contoh soalnya:

0	1	2	3	4	5	6	7	8	9	10
-2	4	0	1	2	8	13	9	10	11	14

1. Cari nilai 8 dengan pencarian linier


Jawab : data diurutkan dahulu
 

0	1	2	3	4	5	6	7	8	9	10
-2	0	1	2	4	8	9	10	11	13	14

8 = -2     (tidak!)
8 = 0       (tidak!)
8 = 1       (tidak!)
8 = 2       (tidak!)
8 = 4       (tidak!) 
8 = 8       (ya!) => output : 5 (index)
 

PENCARIAN BINARY

Pencarian Biner (Bah.Ingg: Binary Search) adalah pencarian data secara eliminasi biner berulang/terus-menerus. Maksudnya adalah pada saat pencarian data, 1 kelompok data yang sudah urut dibagi menjadi 2 subkelompok. Lalu salah satu subkelompok dieliminasi, sehingga ruang lingkup pencarian data menjadi lebih sedikit. Kemudian subkelompok yang tersisa dibagi lagi menjadi 2 subkelompok lagi, demikian dilakukan secara berulang-ulang.

Sebagai contoh, misalnya diinginkan mencari data nama Irawan di sekumpulan data nama yang sudah terurut. Apabila kelompok data ini dibagi 2, ternyata di bagian tengah terdapat nama Leny. Maka subkelompok data sesudah Leny akan dieliminasi, karena tidak mungkin nama Irawan akan terdapat pada data huruf L s/d Z. Sedangkan, subkelompok sebelum Leny, kemudian akan dibagi 2 lagi, dan diperiksa ulang. Ternyata kali ini di bagian tengah terdapat nama Gery. Maka kelompok data sebelum Gery akan dieliminasi, karena tidak mungkin terdapat data Irawan pada huruf A s/d G. Demikian seterusnya terjadi, proses eliminasi ruang lingkup pencarian data menjadi semakin sedikit secara berulang. 

 Berikut adalah 3 fakta penting mengenai pencarian biner:

·         Hanya bisa berfungsi pada data yang sudah terurut (sorted), ini adalah syarat mutlak dari pencarian biner

·         Merupakan salah satu contoh penerapan cara kerja dari konsep Divide and Conquer

·         Kompleksitasnya adalah O(lg n)

Berikut Soal: 

2. Cari nilai 13 dengan pencarian binary 

A = awal, B = tengah, C = akhir

0	1	2	3	4	5	6	7	8	9	10
-2	0	1	2	4	8	9	10	11	13	14
A					B					C

13 > 8 awal = tengah + 1

0	1	2	3	4	5	6	7	8	9	10
-2	0	1	2	4	8	9	10	11	13	14
						A		B		C

13 > 11 awal = tengah + 1

0	1	2	3	4	5	6	7	8	9	10
-2	0	1	2	4	8	9	10	11	13	14
									A=B=C

13 = 13 data ditemukan

Selesai...! 

Referensi : http://yudiprastyo1993.blogspot.com/