第６回 力まかせ探索（フルスキャン）

何かを検索するプログラムを書く場合に、一番簡単かつ分かりやすい方法が「力まかせ探索」とか呼ばれる方法です。「力まかせ探索」はどちらかといえば通称で、正確には名称は存在しないかもしれません。データベースではフルスキャンと呼ばれます。

<?php

function fullscan($needle, $haystack)
{
  $ret = array();
  foreach ($haystack as $key => $val) {
    if ($val === $needle) {
      $ret[] = $key;
    }
  }
  return $ret;
}

$array = array(5, 2, 4, 3, 4, 8, 7, 2, 1);
echo '処理対象：' . join(', ', $array) . "\n";
echo "処理中...\n";
$output = fullscan(2, $array);
echo '2の位置：' . join(', ', $output) . "\n";

処理結果は

処理対象：5, 2, 4, 3, 4, 8, 7, 2, 1
処理中...
2の位置：1, 7

位置は0始まりなので「1, 7」になります。

単純にループを回して全部舐める、単純素朴な方法です。しかし、計算量は探索アルゴリズムで最大の になります。あえてメリットをあげるなら、バグが入り込む余地がほとんどないことです。

入力データに重複がないなら、見つかったところで処理を中断しても良いでしょう。

<?php

function fullscan_unique($needle, $haystack)
{
  foreach ($haystack as $key => $val) {
    if ($val === $needle) {
      return $key;
    }
  }
  return false;
}

$array = array(1, 5, 9, 7, 3, 2, 6, 4, 8);
echo '処理対象：' . join(', ', $array) . "\n";
echo "処理中...\n";
$output = fullscan_unique(2, $array);
echo '2の位置：' . $output . "\n";

処理対象：1, 5, 9, 7, 3, 2, 6, 4, 8
処理中...
2の位置：5

次回は「二分探索」をこれと比較しながら進めます。