ほしいものを はやく さがす

さいしょから じゅんに

さがす いちばん かんたんな ほうほうは
さいしょから 一つずつ 見る ことです。
「これか? ちがう。
つぎは? ちがう。」
あう まで
めくりつづけます。
たしかですが、
うしろに あると
時間が かかります。

まえから 一つずつ。(さがす あたい 13 · まえから 一ますずつ かくにん)

ますが いくつか なら
だいじょうぶ。
でも 何千、何万こ なら?
一つずつ 見ては
だいぶ かかります。
もっと いい ほうほうが あります。
列が そろった ときに つかう
かしこい ほうほうです。

まん中を ひらいてみる

列が そろって いれば
こう します。
まん中を ひらいて 見ます。
さがす あたいが それより 大きければ
まえの 半分は すてます。
小さければ うしろの 半分を すてて。
一ど 見る ごとに
半分が きえます。

まん中を 見て 半分を すてます。(さがす あたい 13 · ない 半分を まるごと すてる)

一どに 半分を すてるから、
のこりが ぐっと へります。
8ますが 4ます、
4ますが 2ます、
2ますが 1ます。
すうかいで
ぴったり 一ますに しぼれます。

一つずつ vs 半分ずつ

二つを ならべて
同じ あたいを さがしましょう。
一つずつは
うしろの あたいまで
なんども 見る ひつようが あります。
半分ずつは
すうかいで おわります。
同じ こたえなのに
あしの かずが ぜんぜん ちがいます。

同じ あたい(13)を さがす、あしの かず くらべ。(一つずつ = おそい · 半分ずつ = はやい)

ますが ふえるほど
さが もっと ひらきます。
千こを 一つずつなら
さいだい 千かい、
半分ずつなら 十かいで すみます。
この さは
大きな データでは
とほうも ありません。

なぜ ならべかえが さきか

半分ずつ きるには
じょうけんが 一つ あります。
列が そろって いる ことです。
ならんで いてこそ
「まん中より 大きければ まえは すてて いい」が
なりたつから。
ばらばらだと
半分を すてられません。

ならんだ ときだけ 半分ずつが つうじます。(列 そろう → なりたつ · ばらばら → だめ)

だから ならべかえと さがしは
あいぼうです。
一ど 列を そろえて おけば、
そのあと さがしが
ずっと はやく なるから。
ととのえる てまが
のちのち むくわれるのです。

ここまで きました

さがしは いつも そばに あります。
じしょ、でんわちょう、
けんさくまどに うった 一ことば。
その うしろで
「半分ずつ きる」ような ほうほうが
はやく こたえを 見つけます。
じゅんばん、ならべかえ、さがしまで
いま 一すじに つながりました。

じゅんばん → ならべかえ → さがし、ここまで。(さがし = ほしいものを はやく つまみだす)

アルゴリズムが
たいそうな ものでは ないと
もう わかるでしょう。
じゅんばんを きめ、
ととのえ、
かしこく さがす こと。
小さな ちえが あつまって
大きな ことを なしとげるのです。