PHPで2分探索を書いてみました。

はじめに

アルゴリズムを学び始めて理解したものから、順にアウトプットしていこうと思います。
2分探索は、「ソート済み配列の中から目的のものを高速に探索する」アルゴリズムになります。

以下、自分なりに書いてみました。

<?php
function binarySearch($value, $array)
{
  $search_flag = false;
  $arrayLeft = 0;
  $arrayRight = count($array) - 1;

  while (abs($arrayLeft - $arrayRight) > 1) {
    $pivot = round(($arrayLeft + $arrayRight) / 2);
    if ($array[$pivot] == $value) {
      $search_flag = true;
      break;
    }
    if ($array[$pivot] < $value) {
      $arrayLeft = $pivot;
    }
    if ($array[$pivot] > $value) {
      $arrayRight = $pivot;
    }
  }


  if (!$search_flag) {
    echo "見つかりませんでした";
  } else {
    echo "見つかりました";
  }
}


$array = [3, 5, 9, 12, 15, 21, 29, 35, 42, 51, 62, 78, 81, 87, 92, 93];

binarySearch(62, $array);
binarySearch(9, $array);
binarySearch(10, $array);

ポイント

while文の中でarrayLeftとarrayRightの要素が隣合わせになったら、処理を終了するという記述になります。
2分探索は、配列がソート済みという条件があるので、ソート関数を使ってから活かせればいいですね。
PHPドキュメント
https://www.php.net/manual/ja/array.sorting.php

以上