第７回 二分探索（バイナリサーチ）

力まかせ探索は でした。二分探索（バイナリサーチ）は です。クイックソートは でしたが、「半分、また半分」のときにlog nが登場します。二分探索も「半分、また半分」です。
詳しい説明はwikipediaで。

力まかせ探索と違い、二分探索はソート済みであることが前提になります。まずはデータに重複がないパターンを書きます。

<?php

// $haystackはソート済みとする。
function binary_search_unique($needle, $haystack)
{
  $left = 0;
  $right = count($haystack) - 1;
  while ($left <= $right) {
    $p = (int)(($left + $right) / 2);  // $p は探索範囲のまんなか
    echo "左:$left, 右:$right, 探索位置:$p\n";

    // 見つかったら位置を返す。
    // 見つからなかった場合、チェックした値が$needleより小さければ、目標は右側半分のなかにあるはず。
    // チェックした値が$needleより大きければ、目標は左側半分のなかにあるはず。
    if ($haystack[$p] === $needle) {
      return $p;
    } elseif ($haystack[$p] < $needle) {
      $left = $p + 1;
    } else {
      $right = $p - 1;
    }

    // $haystackの中に$needleがない場合は、この時点で$left > $rightになるのでループから抜ける。
  }
  return false;
}

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

実行結果は

処理対象：1, 2, 3, 4, 5, 6, 7, 8, 9
処理中...
左:0, 右:8, 探索位置:4
左:0, 右:3, 探索位置:1
2の位置：1

国語辞典を引くときの調べ方に似ています。目的の単語が開いたページの右側にあるのか左側にあるのか。そういう調べ方ができるのは、辞書の単語が整列されているからです。
同じ読みの単語が複数ある時は、もうちょっと工夫が必要です。

function binary_search($needle, $haystack)
{
  $ret = array();

  // まず１つでもヒットする位置を探す。
  // １つでもヒットすれば、その前後が候補位置になる。
  $point = binary_search_unique($needle, $haystack);
  if ($point !== false) {
    $ret[] = $point;
    for ($i = $point - 1; $i >= 0; $i--) {
      if ($haystack[$i] === $needle) {
        $ret[] = $i;
      } else {
        break;
      }
    }
    for ($i = $point + 1; $i < count($haystack); $i++) {
      if ($haystack[$i] === $needle) {
        $ret[] = $i;
      } else {
        break;
      }
    }
  }

  return $ret;
}

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

実行結果は

処理対象：1, 1, 1, 2, 2, 2, 3, 3, 3, 4, 4, 4, 5, 5, 5, 6, 6, 6, 7, 7, 7, 8, 8, 8, 9, 9, 9
処理中...
左:0, 右:26, 探索位置:13
左:0, 右:12, 探索位置:6
左:0, 右:5, 探索位置:2
左:3, 右:5, 探索位置:4
2の位置：4,3,5

ソートしてあるデータを使うことで から になり、データ量が増えても速く見つかるようになりました。これを基本にもっと工夫すると、データベースの「インデックス」が出来上がります。インデックスはあらかじめソートしたデータを用意することで検索を速くしています。
「ソートしてから検索しよう！」という発想が出てきますが、クイックソートでも なので力まかせ探索（フルスキャン）より遅いです。「インデックスは更新が遅い」というのは、更新のたびにソートしなければいけないからです*1。バランスを取る必要があります。

*1:ソートの計算が発生するのに加え、そのデータをディスクに保存する必要があります。ソート自体は「ほぼソートされているデータ」という特性を生かすことで速くできたりもしますが、ディスクアクセスは計算よりはるかに遅いです