Source Code: Penerapan Algoritma Binary Search di PHP

Pada materi sebelumnya, kita sudah membahas tentang pemahaman algoritma binary search. Tidak lengkap rasanya jika kita tidak mencoba menerapkan atau mengimplementasikannya langsung ke dalam kode bahasa pemrograman.

Pada materi ini, kita akan belajar membuat sebuah kode binary search untuk melihat penerapannya secara langsung. Bahasa yang akan kita gunakan kali ini adalah bahasa pemrograman PHP.

Sebelumnya, ada beberapa tool yang perlu dipersiapkan. Yaitu sebuah Text Editor untuk menulis kode dan sebuah Web Server yang mendukung bahasa PHP. Contoh tool web server yang bisa digunakan adalah Xampp atau Ampps.

Persiapan sudah lengkap? Mari kita lanjutkan!

Membuat Binary Search dengan PHP

Sebagai permulaan, kami disini akan menjelaskan implementasi algoritma ini dengan beberapa kasus yang berbeda. Berikut penjelasannya:

Studi Kasus 1

Pada kasus pertama, kita akan membuat sebuah kode yang diletakan di dalam sebuah function. Function tersebut nantinya akan mengembalikan nilai true jika berhasil menemukan data atau mengembalikan nilai false jika tidak ada data yang ditemukan.

Kita di sini akan membuat sebuah function bernama binary_search() yang akan menerima dua parameter berupa $data sebagai data array dan $keyword sebagai kata kunci data yang ingin dicari. Jika dipanggil, function ini akan mengembalikan nilai berupa Boolean.

Perlu diingat, $data yang akan diterima oleh function tersebut harus diurutkan terlebih dahulu dengan function sort(). Berikut ini adalah implementasi algoritma binary search yang ditulis dalam PHP:

<?php

function binary_search($data, $keyword)
{
  $MIN = 0;
  $MID = 0;
  $MAX = (int)(count($data) - 1);

  if($MAX < 0) return false;

  while ($MIN <= $MAX)  
  {
    $MID = $MIN + (int)(($MAX - $MIN) / 2);
    if ($data[$MID] == $keyword)
    {
      return true;
    }else{
      if ($keyword < $data[$MID])
      {
        $MAX = $MID - 1;  
      }else{
        $MIN = $MID + 1;
      }
    }
  }
  return false;
}

$array   = [4,1,6,3,5,7,8,9,2,3,4,6,7,'A','V','Z','X','Q'];
$keyword = 'Q';

sort($array);
$result = binary_search($array, $keyword);

if ($result) 
{
  echo "Data ditemukan!";
}else{
  echo "Data tidak ditemukan!";
}

Penjelasan kode:

Pada code di atas, kami telah menyiapkan data array yang disimpan di dalam variable $array dan sebuah kata kunci pencarian yang disimpan di dalam variable $keyword. Script sort($array) berfungi untuk mengurutkan data yang berada di dalam variable $array.

Setelah semua data sudah siap, kita panggil function binary_search() dengan mengirimkan data yang diperlukan. Dengan begitu, function ini akan mengembalikan nilai true jika data ditemukan atau mengembalikan nilai false jika tidak ditemukan.

Dari kode program di atas, function binary_search() akan mengembalikan nilai true karena nilai yang ingin dicari ‘Q’ berada di dalam data array. Sehingga program akan menghasilkan output Data ditemukan!

Bagaimana? Sudah bisa membaca dan memahami kodenya?

Dari kode di atas, kita sudah menerapkan konsep binary search secara sederhana ke dalam bahasa program. Namun, kode tersebut tidak bisa digunakan untuk menampilkan hasil pencarian karena hanya mengembalikan nilai benar dan salah saja. Untuk itu, di studi kasus selanjutnya kita akan memperbaiki kode di atas agar bisa menampilkan hasil pencarian.

Studi Kasus 2

Kita tahu bahwa kode di atas hanya mengembalikan nilai true dan false saja, bukan hasil dari pencarian.

Pada kasus ke 2 ini, kita akan memodifikasi kode di atas agar bisa menampilkan data hasil pencarian. Jika tadinya function binary_search() mengembalikan nilai Boolean, kita akan mengubahnya agar function tersebut mengembalikan nilai index dari data array. Berikut ini adalah kodenya:

<?php

function binary_search($data, $keyword)
{
  $MIN = 0;
  $MID = 0;
  $MAX = (int)(count($data) - 1);

  if($MAX < 0) return false;

  while ($MIN <= $MAX)  
  {
    $MID = $MIN + (int)(($MAX - $MIN) / 2);
    if ($data[$MID] == $keyword)
    {
      return $MID;
    }else{
      if ($keyword < $data[$MID])
      {
        $MAX = $MID - 1;  
      }else{
        $MIN = $MID + 1;
      }
    }
  }
  return false;
}

$array   = [4,1,6,3,5,7,8,9,2,3,4,6,7,'A','V','Z','X','Q'];
$keyword = 2;

sort($array);
$result = binary_search($array, $keyword);

if ($result) 
{
  echo "Data ditemukan! => " . $array[$result];
}else{
  echo "Data tidak ditemukan!";
}

Penjelasan kode:

Pada kode di atas, hanya terjadi perubahan pada script return false menjadi return $MID. Dengan begitu, function binary_search() akan mengembalikan nilai index data array jika data ditemukan atau mengembalikan nilai false jika tidak ditemukan.

Untuk mendapatkan nilai hasil pencarian, kita cukup menggunakan $array[$result]. Dengan cara seperti ini, hasil pencarian akan dapat ditampilkan oleh program.

Kesimpulan

Pada materi ini kita telah belajar membuat sebuah script algoritma binary search sederhana dengan PHP. Namun, script di atas masih memiliki banyak kekurangan sehingga perlu pengembangan lebih lanjut.

Sangat lucu jika setiap melakukan pencarian data, program hanya menampilkan satu hasil pencarian saja. Karena di beberapa kasus, di dalam data array terdapat data yang sama. Sehingga data-data tersebut harus ditampilkan sebagai hasil pencarian atau disebut sebagai multiple matches.

Pada meteri selanjutnya, kita akan mengembangkan script di atas untuk mengatasi masalah tersebut.