わかりやすく 探索アルゴリズム とは

最初から順番に

いちばん簡単な探し方は、最初から一つずつ見ることです。
「これかな？ 違う。次は？ 違う」。見つかるまでめくり続けます。
確実ではありますが、探す値が後ろのほうにあると時間がかかります。

「一つずつ探す」を押すと、前から一マスずつ確かめます。探す値は13。

マスが少なければ、それでかまいません。
でも何千、何万とあったら、一つずつ見ていてはとても時間がかかります。
もっとよい方法があります。列がそろっているときに使える、賢い方法です。

真ん中を開く

列がそろっていれば、こうします。まず真ん中を開いて見ます。
探す値がそれより大きければ前半分を捨て、小さければ後ろ半分を捨てます。
一回見るたびに、半分が消えるのです。

「真ん中を見る」を押すたびに、探す値のない半分をまるごと捨てます。探す値は13。

一度に半分を捨てるので、残りがぐっと減ります。
8マスが4マスに、4マスが2マスに、2マスが1マスに。
何回かで、たった一マスまで絞り込めます。

一つずつ vs 半分ずつ

二つを並べて、同じ値を探してみます。
一つずつ探すほうは、後ろにある値まで何度も見なければならず、半分ずつのほうは何回かで終わります。
答えは同じなのに、歩数がまるで違います。

同じ値(13)を探して、歩数を比べます。一つずつ = 遅い · 半分ずつ = 速い。

マスが増えるほど、差は広がります。
千個を一つずつ見ると最大で千回かかりますが、半分ずつなら十回ほどですみます。
この差は、大きなデータではとてつもないものになります。

なぜ並べ替えが先なのか

半分ずつ切るには、条件が一つあります。列がそろっていることです。
並んでいてこそ、「真ん中より大きければ前は捨ててよい」が成り立つからです。
ばらばらなら、半分を捨てることはできません。

並んでいるときだけ、半分ずつ切る方法が使えます。列がそろう → 成り立つ · ばらばら → 成り立たない。

だから並べ替えと探索は、相棒どうしです。
一度列をそろえておけば、そこから先はずっと速く探せます。
整えるのにかけた手間が、いつまでも報われるのです。

ここまで来た道

探すことは、いつも身近にあります。
辞書、電話帳、検索窓に打った一つの言葉。その裏では、半分ずつ切るような方法が素早く答えを見つけています。
順番、並べ替え、探索まで、これで一本につながりました。

順番 → 並べ替え → 探索、ここまで来ました。探索 = ほしいものを素早く取り出すこと。

もうわかったでしょう。アルゴリズムはたいそうなものではありません。
順番を決め、整え、賢く探すこと。
小さな工夫が集まって、大きなことをやってのけるのです。