今回は配列内を検索する手段として二分探索という方法を紹介したいと思います。
状況は限られていますが、適用できれば非常に強力な方法です。
二分探索
図とコード(PHP)を使って解説していきます
図解
例えば以下のような配列が存在し、数値の21を探したいとします。
※配列の中はあらかじめソートされていると前提します。
上記の配列から特定の数字を探す場合、どういった方法が良いのでしょうか？
通常探索
まず順番に探していく場合、下記のとおりになります。
ご覧の通り、順番に探していく場合はかなり手間になります。
二分探索
二分探索の場合はどうでしょうか。
まず配列の真ん中にある数値を探索します。
今回だと「(0 + 10) / 2 = 5」になるので配列の真ん中は[5]であることが分かります。
配列[5]の中には数値15が入っています。探したい数値は21なのでまだ正解にはたどり着いていません。
しかし、配列[5]以降に探している数値21はあることが分かりました。
次は配列[6]から[10]の真ん中を見に行きます。
「(6 + 10) / 2 = 8」になるので次は配列[8]の値をチェックします。
すると、配列[8]の中身は21ですね。これで正解の数値にたどり着きました。
このように探索する回数を減らして目的の数値を探せる方法が「二分探索」です。
コード
では次はコードと簡単な処理時間を比較してみたいと思います。コードはPHPで記載されています。
数値が1-100000まで入った配列からランダムに数値を探索するという内容を1000回ループさせて実行時間を計測します。
通常の場合(for文)
まずは配列の最初から探索していく方法を試してみたいと思います。
for文で実行します。
<?php
// 配列作成
$test_list = range(1, 100000);
// 計測開始
$start_time = microtime(true);
// 1000回繰り返し
for ($count = 0; $count < 1000; $count++) {
// 探す数値を決定
$search_num = rand(1, 100000);
// 数値を探す
for ($i = 0; $i < count($test_list); $i++) {
if ($search_num === $test_list[$i]) {
echo $search_num . '->' . $test_list[$i] . PHP_EOL;
break;
}
}
}
// 計測終了
$end_time = microtime(true);
// 経過時間
$time = $end_time - $start_time;
echo '平均:' . ($time / 1000) . '秒' . PHP_EOL; //平均:0.00093360686302185秒
echo '合計:' . $time . '秒' . PHP_EOL; //合計:0.93360686302185秒
上記の結果でした。for文以外は果たしてどうなるでしょうか。
PHPの場合(array_search()関数)
PHPには指定した値を配列で検索し、見つかった場合に対応する最初のキーを返すarray_search()関数が存在します。
次はその関数で実行してみたいと思います。
<?php
// 配列作成
$test_list = range(1, 100000);
// 計測開始
$start_time = microtime(true);
// 1000回繰り返し
for ($count = 0; $count < 1000; $count++) {
// 探す数値を決定
$search_num = rand(1, 100000);
// 数値を探す
for ($i = 0; $i < count($test_list); $i++) {
$res = array_search($search_num, $test_list, true);
if ($res) {
echo $search_num . '->' . $test_list[$i] . PHP_EOL;
break;
}
}
}
// 計測終了
$end_time = microtime(true);
// 経過時間
$time = $end_time - $start_time;
echo '平均:' . ($time / 1000) . '秒' . PHP_EOL; //平均:0.00015707898139954秒
echo '合計:' . $time . '秒' . PHP_EOL; //合計:0.15707898139954秒
for文より早いですね、二分探索はどうなるのでしょうか。
二分探索の場合
最後に、二分探索で実行してみたいと思います。
<?php
// 配列作成
$test_list = range(1, 100000);
// 計測開始
$start_time = microtime(true);
// 1000回繰り返し
for ($count = 0; $count < 1000; $count++) {
// 探す数値を決定
$search_num = rand(1, 100000);
// 数値を探す
$start = 0;
$end = count($test_list) - 1;
while ($start <= $end) {
$middle = (int)(($start + $end) / 2);
if ($test_list[$middle] === $search_num) {
echo $search_num . '->' . $test_list[$middle] . PHP_EOL;
break;
} elseif ($test_list[$middle] < $search_num) {
$start = $middle + 1;
} else {
$end = $middle - 1;
}
}
}
// 計測終了
$end_time = microtime(true);
// 経過時間
$time = $end_time - $start_time;
echo '平均:' . ($time / 1000) . '秒' . PHP_EOL; //2.7949810028076E-6秒
echo '合計:' . $time . '秒' . PHP_EOL; //0.0027949810028076秒
for文やarray_search()関数より圧倒的に早いという結果になりました。
まとめ
このように二分探索は特定の条件下で配列内を高速に探索することが可能な手法です。
もし競技プログラミング等に参加している方はよく使うのでぜひ覚えておきたいですね。
最後まで読んでいただき、ありがとうございました。