SEARCHING (SEQUENTIAL SEARCH DAN BINARY SEARCH)

Pencarian (Searching) merupakan proses untuk  menemukan data (nilai) tertentu yang ada dalam sekumpulan data yang bertipe sama. Fungsi pencarian itu sendiri adalah untuk mencocokkan data.

Ada 2 metode dalam Searching, yaitu:

1. Metode Pencarian Beruntun (Sequential Search)

Sequential Search merupakan konsep pencarian pada array 1 dimensi dimana metode yang digunakan adalah membandingkan data-data (nilai-nilai) yang terdapat di dalam kumpulan data tersebut, mulai dari data pertama sampai dengan nilai yang dicari ditemukan atau membandingkan dari nilai pertama sampai nilai terakhir tanpa pengurutan data-data terlebih dahulu, jika data yang dicari telah ditemukan maka proses pencarian dihentikan.

Misalkan ada 7 data dalam array A  

Data yang akan dicari adalah 1, misal X = 1

Pertama kita membandingkan X dengan nilai pertama 12, jika nilai yang dibandingkan dengan X tidak sama maka dilanjutkan ke nilai berikutnya yaitu 5, 23, 47 , 1 (nilai ditemukan pada indek ke 4)

Berikut ini contoh program Sequential Search

Hasil run program:

2. Metode Pencarian Bagi Dua (Binary Search) 

Metode ini diterapkan pada sekumpulan data dalam suatu array yang sudah terurut (ascending (kecil ke besar) atau descending (besar ke kecil)). Metode ini lebih cepat dibandingkan metode Sequential Search, akan tetapi metode ini memiliki kelemahan jika ada 2 data yang sama maka hanya 1 yang akan ditemukan.

Konsep dasar metode ini adalah membagi 2 jumlah data (nilai), dan menentukan apa data yang berada ditengah bernilai sama, lebih dari atau kurang dari nilai data yang akan dicari. Jika bernilai sama, maka langsung data yang dicari ditemukan.

Jika data terurut secara ascending, maka nilai data yang ada di tengah kurang dari data yang dicari, maka pencarian selanjutnya dimulai dari di data tengah ke kanan, dan begitu seterusnya sampai ketemu atau tidak sama sekali. Dan sebaliknya nilai data yang berada di tengah lebih dari data yang dicari, maka pencarian selanjutnya dimulai di data tengah ke kiri, dan begitu seterusnya sampai ketemu atau tidak sama sekali. Dan begitu juga untuk data yang terurut secara descending.

Langkah-langkah untuk metode Binary Search :

• Urutkan data dari indeks 0 sampai n-1 (kanan ke kiri) apakah ascending atau descending
• Cari posisi tengah pada data (posisi awal (indeks ke-0) + posisi akhir (indeks ke-n) / 2), misalkan jika saat membagi mendapat hasil 6,5 maka abaikan ,5 gunakan 6
• Bandingkan data yang dicari dengan data ditengah
• Jika lebih kecil, maka pencarian dimulai dari posisi awal adalah posisi tengah -1
• Jika lebih besar, maka pencarian dimulai dari posisi awal adalah posisi tengah +1
• Jika data sama berarti data ditemukan

Misalkan ada 9 data terurut secara ascending A[9] = { 2, 7, 11, 16, 21, 22, 29, 31, 99}
carilah data X = 31

Penyelesaian :

1.  Karena data sudah diurutkan maka langsung saja cari posisi tengah

Posisi awal + posisi akhir / 2

(0 + 8) / 2 = 4 jadi posisi tengah berada pada indeks ke 4

2. Bandingkan data yang dicari X=31 dengan data yang ditenganh 21

31 > 21 maka posisi tengah + 1 (langkah ke 5)

3. Abaikan data yang berada di kiri, karena posisi tengah +1 maka posisi awal dimulai dari indeks ke 5 dan posisi akhir indeks ke 8

4.  Ulangi langkah ke 2, posisi awal + posisi akhir /2

(5 + 8) / 2 = 6,5 abaikan ,5. Jadi posisi tengan adalah indeks ke 6

5.  Bandingkan x=31 dengan data tengah 31

 31 = 31 , data yang dicari sama dengan data yang berada di posisi tengah. Jadi data ada di indeks ke 6.

Berikut ini contoh program Binary Search

Hasil run program:

Contoh hasil build program diatas menggunakan Borland C++. Mungkin hanya sekian penjelasan tentang Searching (Sequential search dan Binary search) dari saya kurang lebihnya. Jika ada yang ingin ditanyakan dapat ditanyakan pada kolom komentar dibawah ini. Terimakasih telah berkunjung ke blog saya :v





Sumber :
KONSEP DAN APLIKASI PEMROGRAMAN MENGGUNAKAN BORLAND C++ BUILDER 6 M. Fachrurrozi