My first Magazine pemrograman-kompetitif-dasar | Page 35

3
Pencarian dan Pengurutan
Pencarian dan pengurutan merupakan hal sederhana dan sering digunakan dalam pemrogram-
an. Terdapat berbagai macam cara untuk melakukan pencarian maupun pengurutan. Membahas
beberapa cara tersebut dapat memberikan gambaran bagaimana sebuah persoalan diselesaikan
dengan berbagai algoritma.
3.1
Pencarian
Contoh Soal 3.1: Sepatu untuk Bebek
Kwek, salah satu bebek Pak Dengklek akan segera merayakan ulang tahunnya. Pak
Dengklek akan memberikan Kwek hadiah ulang tahun berupa sepatu. Terdapat N sepatu
di toko. Sepatu ke-i memiliki ukuran sebesar h i . Pak Dengklek tahu bahwa ukuran kaki
Kwek adalah sebuah bilangan bulat X. Karena N bisa jadi sangat besar, Pak Dengklek
meminta bantuan kalian untuk mencari sepatu keberapa yang cocok dengan ukuran kaki
Kwek. Bantulah dia!
Batasan
• 1 ≤ N ≤ 100.000
• 1 ≤ X ≤ 100.000
• 1 ≤ h i ≤ 100.000, untuk 1 ≤ i ≤ N
Kita dihadapkan pada persoalan pencarian: diberikan N angka. Cari apakah X ada di antara
angka-angka tersebut. Jika ditemukan, cetak di urutan keberapa angka tersebut berada.
3.1.1
Sequential Search
Salah satu ide yang muncul adalah dengan melakukan pengecekan kepada seluruh elemen
yang ada. Dengan kata lain, kita akan melakukan:
• Periksa satu per satu dari sepatu pertama, kedua, ketiga, dan seterusnya.
• Jika ditemukan, langsung laporkan.
• Jika sampai akhir belum juga ditemukan, artinya angka yang dicari tidak ada pada daftar.
Implementasi ide tersebut dapat dilihat di Algoritma 10.
25