Membuat Binary Search Multiple Results di PHP

Pada materi sebelumnya, kita telah belajar cara membuat kode binary search di PHP dengan hasil pencarian berupa boolean dan index data. Namun, pada kode tersebut hanya mengembalikan satu nilai saja.

Dalam proses pencarian, biasanya terdapat beberapa data yang merupakan hasil pencarian data tersebut. Akan sangat lucu jika di dalam sebuah data terdapat beberapa data yang sama namun di dalam proses pencarian hanya menampilkan satu data saja. Oleh karena itu, pada materi kali ini kita akan sedikit mengubah kode sebelumnya agar pencarian binary search yang telah kita buat menghasilkan multiple results atau multiple matches.

Maksudnya gimana ya, kok saya belum paham?

Jadi begini, misalnya kita mempunyai data nama buah berupa array di bawah ini.

['srikaya', 'jeruk', 'apel', 'rambutan', 'apel', 'kelengkeng', 'durian', 'apel']

Ketika kita melakukan pencarian dengan keyword apel menggunakan kode binary search sebelumnya, program akan menghasilkan satu data yaitu apel. Namun, di dalam array tersebut terdapat tiga data apel yang seharusnya merupakan hasil dari pencarian. Jadi, seharusnya program menghasilkan tiga data dari proses pencarian tersebut.

Tidak usah lama-lama, mari kita pecahkan permasalahan itu bersama.

Binary Search Multiple Results

Apa yang akan kita lakukan?

Dalam membuat sebuah program kita harus memikirkan terlebih dahulu sebuah skenario, alur program, dan teknik yang akan kita gunakan. Berikut ini adalah scenario atau alur program pencarian yang akan kita buat untuk menjawab persoalan di atas.

1. Menemukan index data dengan binary search.
2. Memeriksa data di sekitar hasil pencarian yang juga merupakan hasil dari pencarian.
3. Menentukan nilai index MIN dan MAX di sekitar hasil pencarian.
4. Mengubah nilai index MIN dan MAX menjadi range data berupa array.
5. Mengembalikan data array sebagai hasil pencarian.

Masih belum jelas dengan alurnya? Mari kita jabarkan!

Sebelumnya saya akan menyediakan sebuah data yang sudah terurut untuk mempermudah dalam menjelaskannya. Berikut ini adalah datanya.

['apel', 'apel', 'apel', 'durian', 'jeruk', 'kelengkeng', 'rambutan', 'srikaya']

Dalam pencarian biner, akan didapatkan nilai index 1 dari data di atas. Setelah itu, kita akan melakukan proses pengecekan data di sekitar index 1. Teknik yang akan kita gunakan untuk melakukan pengecekan ini adalah teknik linear looping atau pengecekan secara berurut. Teknik ini bias diibaratkan seperti algoritma linear search.

Dengan teknik linear looping, kita akan mengecek data ke arah kiri satu persartu dari index 1 untuk mendapatkan nilai index awal (MIN), lalu mengecek data ke arah kanan satu persatu dari index 1 untuk mendapatkan nilai index akhir (MAX). Dengan begitu, akan didapatkan nilai MIN = 0 dan MAX = 2.

Setelah menemukan titik awal dan titik akhir, kita harus membuat range data dari kedua titik tersebut dengan menyimpannya ke dalam array. Setelah itu, kita bias mengembalikan array tersebut sebagai output dari program pencarian kita.

Dengan seperti itu, kita akan mendapatkan data [0, 1, 2] yang merupakan index hasil pencarian dari data yang ingin kita cari. Sehingga kita bisa menampilkan data hasil pencarian data data index tersebut.

Apa yang akan terjadi jika data tidak ditemukan?

Jika tidak ditemukan data yang cocok, program akan mengembalikan data berupa array kosong.

Berikut ini adalah source code binary search multiple result di PHP.

<?php

/**
 *  Binary Search Multiple Matches
 */

function get_multiple_matches($data, $keyword, $res)
{
  $MIN = $MAX = $res;
  $min_res = $max_res = false;

  while ($min_res == false) 
  {
    if(!isset($data[$MIN - 1]))
    {
      $min_res = true;
    }else{

      if($data[$MIN] == $keyword AND $data[$MIN - 1] != $keyword)
      {
        $min_res = true;
      }else{
        $MIN--;
      }
    }
  }

  while ($max_res == false) 
  {
    if(!isset($data[$MAX + 1]))
    {
      $max_res = true;
    }else{

      if($data[$MAX] == $keyword AND $data[$MAX + 1] != $keyword)
      {
        $max_res = true;
      }else{
        $MAX++;
      }
    }
  }

  return array_merge(range($MIN, $MAX));
}

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

  if($MAX < 0) return $res;

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

$array   = ['srikaya', 'jeruk', 'apel', 'rambutan', 'apel', 'kelengkeng', 'durian', 'apel'];
$keyword = 'apel';

sort($array);

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

if ($result) 
{
  echo "Data ditemukan! => ";

  for ($i=0; $i < count($result); $i++) 
  { 
    echo $array[$result[$i]];
    echo " ";
  }

}else{
  echo "Data tidak ditemukan!";
}

Silakan copy paste kode di atas dan lakukan berbagai eksperimen untuk memahami konsep pencarian biner ini lebih mendalam.