Pythonでアルゴリズム学習!二分探索と線形探索を比較してみた

  • このエントリーをはてなブックマークに追加

Pythonコーディングのスキルアップのために、アルゴリズムの学習をしようと思います。ここでは探索アルゴリズムの基礎である二分探索をPythonコードで実装し、線形探索と比較してみました。

こんにちは。wat(@watlablog)です。ここでは探索アルゴリズムの1つ、二分探索をコーディングし、線形探索と比較してみます

線形探索と二分探索の概要

探索とは?

探索(Search)とは、ある集合から目的の要素を探すことです。

例えば、「Search」という単語を辞書から探す問題を解くのも探索問題です。

辞書の1ページ目から「Search」を探していくことも可能ですが、辞書はアルファベット順にソートされているのでSの欄から見始めた方がはやく見つかりそうです。このように、よく考えると効率良く問題を解決できそうな場合はアルゴリズムが威力を発揮します。

前者のように最初から順番に探索してく方法を線形探索(Linear Search)と呼びますが、今回紹介する探索アルゴリズムは二分探索(Binary Search)と呼ばれるアルゴリズムです。単に英語のままバイナリサーチと呼ばれることもあります。

探索アルゴリズムの目標

探索アルゴリズムの目標は、ずばり目的の値が全体のどこに位置しているかを特定することです。以下の図はyが0〜100までの値をとり、65というデータがどこにあるかを探索する問題の例です。

二分探索の目的

探索アルゴリズムを使うためには、事前にデータをソートしておく必要があります。ソートについては以下の記事で解説しているので、是非ご覧下さい。
Pythonコードと図解で理解するバブルソートのアルゴリズム
Pythonで選択ソートのアルゴリズムを実装する方法【動画付】

フローチャートとアニメーションによる解説

線形探索

プログラムを書き始める前に、フローチャートで探索アルゴリズムの流れを見ていきましょう。まずは以下に線形探索のフローチャートを示します。

データAを配列として定義し、keyで探索する数値を指定します。線形探索は単純にデータAの中身を順番に取り出し、keyと比較していくという流れなので大変簡単ですね。

ちなみに、このフローチャートでは探索してもkeyが見つからない場合はNaN(Not a Number)を返す仕様です。

線形探索のフローチャート

線形探索の処理の様子を1コマずつアニメーションで見ていくと以下のGIF動画のようになります。青いソートされたデータの中に赤いターゲットanswerが一つあり、小さい値から順番にサーチしている様子が一目瞭然です。

線形探索のアニメーション

アルゴリズムは大変シンプルでわかりやすいのですが、少しじれったさがありますね。

二分探索

続いて二分探索のフローチャートを以下に示します。上の線形探索と比べるとやや複雑に見えますが、臆せず見ていきましょう。

まず、leftとrightという変数を用意し、「left < right」という条件が満たされている間ループを回します。

leftとrightの中間位置をmidという変数に格納し、data[mid]がkeyでない場合は各変数の大小関係によってleftとrightを書き換えます。

上記フローチャートの処理を1コマずつ見てみると、以下のGIF動画のようになります。「二分」という名の通り、データを半分ずつサーチし、目的の位置に迫っていく様子が一目瞭然です。

二分探索のアニメーション

線形探索が66回の計算で正解に辿り着いたのに対し、二分探査はわずか6回の計算で達成しています。

頭良い!

Pythonコード

それでは遅くなりましたが、線形探索と二分探索の両アルゴリズムをPythonコードで書いていきましょう。

線形探索のコード

まずは線形探索のPythonコードです。ここではdef関数形式で記述しています。フローチャートのシンプルさをそのままなのでこちらは簡単でしょう。

二分探索のコード

続いて二分探索のPythonコードを以下に示します。
フローチャートそのままですが、ループにwhileを使っているところ、if, elif, elseを使って条件分岐をしているところが特徴です。

処理回数とオーダー

線形探索のオーダー

探索アルゴリズムは目的の値が見つかれば終了なので、明確な処理回数は決まっていませんが、線形探索は最大でN回ループが回ります(データ準備に行うソート分は含みません)。

そのため線形探索のオーダーは\(O(N)\)と表現します。

二分探索のオーダー

二分探索はN個の要素数を1になるまで2で割っていくことができる最大数が最悪処理回数になります。

そのためオーダーは\(O(\log_{2} N)\)と書きますが、O記法では底は無視しておおざっぱに書くらしいので、\(O(\log N)\)となります。

線形探索と二分探索の比較コード

Advertisements

検証用コードで処理速度を確認

以下のコードは線形探索と二分探索の処理時間を比較するコードです。
時間の差がわかりやすくなるように100万要素作っています。

以下が実行結果です。目的のkeyを発見するのに線形探索では0.2[s]もかかっているのに対し、二分探索は\(2.4 \times 10^{-5}\)[s]と非常に短い時間でした。アルゴリズムの効果はテキメンです。

おまけ:アニメーション作成用コード

本記事に説明で使っていたアニメーションはもちろんPythonで画像を作っています。コードの効率は全く考えていない内容ですが、メモ程度に残しておきます(主に自分用)。

アルゴリズムの学習は可視化をすると理解が深まるので是非遊んでみて下さい。

線形探索

二分探索

まとめ

本記事では探索アルゴリズムとして線形探索と二分探索の概要を紹介し、フローチャート、図解アニメーション、Python関数による表現、処理時間の検証を行いました。

\(O(\log N)\)オーダーの二分探索は大変強力な探索アルゴリズムであることが確認できました。

アルゴリズムの違いでこんなに処理時間が変わるのは驚きです!
Twitterでも関連情報をつぶやいているので、wat(@watlablog)のフォローお待ちしています!

  • このエントリーをはてなブックマークに追加

SNSでもご購読できます。

コメントを残す

*