今週は、アルゴリズムを勉強しました。
サーチアルゴリズム
データの中を探索して、指定した要素を取り出すアルゴリズムです。
基本的なサーチアルゴリズムは、リニアサーチとバイナリサーチの2種類があります。
リニアサーチ（線形探索）
配列の最初の値から順番に1つずつ検証していって指定した値を探す方法です。
簡単ですが、大量のデータを扱うには不向きです。
1~1000までの配列から777を取り出すプログラムをPHPで実装してみます。
<?php
$list = range(1 ,1000 ,1);
$ans = 777;
for ($i=0; $i < 1000; $i++) {
if ($list{$i} == $ans){
echo $ans;
break;
}
}
?>
バイナリサーチ
まず、配列の中央から検証して、その値が指定した値より大きいか小さいかを比較します。
大きい場合は探索範囲を中央より後半にして、小さい場合は探索範囲を中央より前半にします。
これを繰り返すことで、指定した値を取り出します。
基本的にリニアサーチよりも早いですが、予めデータが昇順または降順にソートされていないと使えません。
同じく、1~1000までの配列から777を取り出すプログラムをPHPで実装してみます。
<?php
$list = range(0, 1000, 1);
$first = 0;
$last = 1000;
$ans = 777;
do{
$center = (($first + $last) / 2);
if ($list[$center] == $ans){
echo $ans;
break;
}
else if ($list[$center] < $ans) {
$first = $center + 1;
}
else if ($list[$center] > $ans){
$last = $center - 1;
}
}
while($first <= $last);
?>