Searching

 Pengertian Searching

Adalah proses mendapatkan (retrieve) information berdasarkan kunci (key) tertentu dari sejumlah informasi yang telah disimpan

Kunci (key) digunakan untuk melakukan pencarian record yang diinginkan didalam suatu list

Contoh: 

Single Match: Siapa Nama Mahasiswa dengan NIM 08001234

Multiple Match: Siapa saja yang mendapat nilai >= 85

Metode Search

1. Sequential Search

teknik yang sederhana dan langsung dapat digunakan pada struktur data baik array maupun linked-list. 

Pencarian data secara urut mulai dari data pertama sampai kunci yang dicari ditemukan atau sampai seluruh data telah dicari dan tidak ditemukan

Dilakukan pada data yang tidak terurut

-Disebut juga linear search atau Metode pencarian beruntun.

-Tidak efisien untuk data dengan list yang besar

-Suatu teknik pencarian data yang akan menelusuri tiap elemen satu per-satu dari awal sampai akhir. 

-Data awal = tidak harus dalam kondisi terurut.

Algoritma Sequential Search

1. Input x (data yang dicari)

2. Bandingkan x dengan data ke-i sampai n

3. Jika ada data yang sama dengan x maka cetak pesan “Ada”

4. Jika tidak ada data yang sama dengan x cetak pesan “tidak ada”

Contoh:

             Nim Nama          IPK

[0] 2207023006 Mulyadi            2.94

[1] 2207023004 Willy Johan        3.15

[2] 2207023003 Anthony Liberty 2.78

[3] 2207023007 Ferry Santoso    3.37

[4] 2207023005 Jaya Mulya      2.93

[5] 2207023001 Budi Santoso  3.01

[6] 2207023008 Indra Gunawan 3.56

[7] 2207023002 M. Rudito W 3.44

Kunci pencarian? 2207023007 

NIM[0] == kunci? --> tidak

NIM[1] == kunci? --> tidak

NIM[2] == kunci? --> tidak

NIM[3] == kunci? --> ya --> Ferry Santoso, 3.37

2. Binary Search

Pencarian data dimulai dari pertengahan data yang telah terurut

Jika kunci pencarian lebih kecil daripada kunci posisi tengah, maka kurangi lingkup pencarian pada separuh data pertama

Begitu juga sebaliknya jika kunci pencarian lebih besar daripada kunci tengah, maka pencarian ke separuh data kedua

Teknik Binary Search hanya dapat digunakan pada sorted array, yaitu array yang elemen-elemennya telah terurut.

-Lebih cepat dari sequential search

-Teknik pencarian = data dibagi menjadi dua bagian untuk setiap kali proses pencarian.

-Data awal harus dalam kondisi terurut. Sehingga harus dilakukan proses sorting terlebih dahulu untuk data awal.

-Mencari posisi tengah: (posisi awal + posisi akhir) / 2 

Algoritma Binary Search 

1. Data diambil dari posisi awal 1 dan posisi akhir N

2. Kemudian cari posisi data tengah dengan rumus: (posisi awal + posisi akhir) / 2

3. Kemudian data yang dicari dibandingkan dengan data yang di tengah, apakah sama atau lebih kecil, atau lebih besar?

4. Jika data sama, berarti ketemu.

5. Jika lebih besar, maka ulangi langkah 2 dengan posisi awal adalah posisi tengah + 1

6. Jika lebih kecil, maka ulangi langkah 2 dengan posisi akhir adalah posisi tengah – 1

Contoh:

Kunci pencarian? 2207023060 

[0] 2207023010            <-- Lo

[1] 2207023020  

[2] 2207023030

[3] 2207023040            <-- Mid

[4] 2207023050                            <-- Lo

[5] 2207023060                            <-- Mid          

[6] 2207023070            <-- Hi      <-- Hi

[7] 2207023080

Ditemukan pada indeks [5] --> Budi Santoso 3.01

3. Interpolatian Search 

Pencarian dilakukan pada posisi relatif kunci terhadap data yang terurut

metode ini didasari pada proses pencarian nomor telepon pada buku telepon

Rumus:

                kunci – data[low]

posisi = -------------------------- x (high – low) + low

    data[high] – data[low]

Contoh:

Kunci pencarian? 088

Low = 0, high = 7

Posisi = (088-025)/(096-025)x(7-0)+0 = 6

Buku[6]==kunci? --> ya

--> Algebra Mastering

--> Zohar Manna