Pencarian: pencarian linear dan biner

Untuk menemukan satu nama dalam daftar terurut berisi sejuta nama, pencarian biner tidak pernah butuh lebih dari 20 kali pemeriksaan.

Mencari satu nilai

Pencarian adalah masalah menemukan letak sebuah nilai dalam sekumpulan data, atau mengetahui bahwa nilai itu tidak ada. Ponselmu melakukannya saat kamu mengetik nama kontak, toko melakukannya saat memeriksa apakah suatu barang masih ada stoknya, dan pemeriksa ejaan melakukannya untuk setiap kata yang kamu ketik. Masukannya adalah sebuah daftar dan nilai target. Keluarannya adalah posisi target, atau tanda seperti -1 yang berarti "tidak ditemukan".

Pencarian linear: satu per satu

Metode paling sederhana adalah mulai dari kiri dan memeriksa setiap nilai bergiliran sampai target ditemukan atau daftarnya habis. Inilah pencarian linear. Cara ini bisa dipakai pada daftar apa pun, terurut atau tidak. Biayanya bergantung pada keberuntungan: kalau target ada di posisi pertama, satu pemeriksaan sudah cukup; kalau target ada di posisi terakhir atau tidak ada, kamu memeriksa setiap nilai. Untuk daftar berisi n nilai, kasus terburuknya n kali pemeriksaan. Daftar yang dua kali lebih panjang bisa butuh pemeriksaan dua kali lebih banyak, dan dari situlah nama "linear" berasal: pekerjaannya bertambah mengikuti garis lurus seiring ukurannya.

function linearSearch(list, target) {
  for (let i = 0; i < list.length; i++) {
    if (list[i] === target) return i;  // ketemu
  }
  return -1;                             // semua sudah diperiksa
}

Pencarian biner: bagi dua sisanya

Kalau daftarnya terurut, kamu bisa jauh lebih cepat. Bayangkan permainan tebak angka: seseorang memilih bilangan dari 1 sampai 100 dan hanya menjawab "lebih tinggi" atau "lebih rendah". Pemain yang cerdik menebak 50 lebih dulu. Apa pun jawabannya, separuh kemungkinan langsung hilang. Tebakan berikutnya adalah tengah-tengah dari yang tersisa, dan seterusnya. Pencarian biner melakukan persis hal ini pada daftar terurut. Pencarian ini memakai dua penanda, lo dan hi, yang mengapit bagian tempat target masih mungkin berada. Pencarian memeriksa nilai tengahnya. Kalau itu targetnya, selesai. Kalau nilai tengah lebih kecil daripada target, semua nilai di sebelah kirinya juga lebih kecil, jadi lo berpindah melewati tengah. Kalau lebih besar, hi berpindah ke sebelum tengah. Saat lo melewati hi, tidak ada yang tersisa dan target tidak ada dalam daftar.

function binarySearch(list, target) {
  let lo = 0, hi = list.length - 1;
  while (lo <= hi) {
    const mid = Math.floor((lo + hi) / 2);
    if (list[mid] === target) return mid;
    if (list[mid] < target) lo = mid + 1;  // target ada di kanan
    else hi = mid - 1;                     // target ada di kiri
  }
  return -1;
}

Berapa kali pemeriksaan?

Setiap pemeriksaan dalam pencarian biner paling sedikit membagi dua bagian yang tersisa. Mulai dari n nilai, setelah satu pemeriksaan tersisa paling banyak sekitar n/2, setelah dua sekitar n/4, dan seterusnya sampai tinggal satu nilai. Banyaknya pembagian dua yang diperlukan untuk turun dari n ke 1 adalah logaritma basis 2 dari n, ditulis log₂ n. Kalau pemeriksaan terakhir ikut dihitung, pencarian biner butuh paling banyak ⌊log₂ n⌋ + 1 pemeriksaan, dengan ⌊ ⌋ berarti dibulatkan ke bawah. Untuk 100 nilai, hasilnya 7 pemeriksaan, karena itulah permainan tebak angka selalu bisa dimenangkan dalam 7 tebakan. Untuk 1000 nilai hasilnya 10, untuk sejuta 20, dan untuk satu miliar 30.

Syaratnya: daftar harus terurut

Pencarian biner hanya berhasil karena dalam daftar terurut, satu perbandingan memberi tahu di sisi mana target pasti berada. Pada daftar yang tidak terurut, nilai tengah tidak memberi tahu apa pun tentang tetangganya, jadi kamu kembali ke pencarian linear. Mengurutkan juga butuh kerja (dua bab berikutnya membahasnya), jadi pilihannya bergantung pada pemakaian. Kalau kamu mencari dalam sebuah daftar sekali saja, pencarian linear mungkin paling murah. Kalau kamu mencari dalam daftar yang sama ribuan kali, mengurutkannya sekali lalu memakai pencarian biner cepat terbayar. Tawar-menawar antara menyiapkan data dan menjawab pertanyaan tentang data itu muncul di seluruh bidang ini.