数学愛好会の話が続きます。
わたしが話した小ネタは?と質問をいただきましたので、ブログでも発表しますね。
最初にしたのは、『バイナリーサーチ』の話です。
辞書で英単語を調べるときのことを思い浮かべてください。
たとえば『music』を調べるとして、
真ん中あたりを開いてみる
↓
もし『p~』という単語が出ていたら、
調べたい『m』項は、それより前にあるので
↓
少し前のあたりを開いてみる
↓
もし『mail』が出てきたら、近いけれど、少し前に行き過ぎている
↓
『music』まで、パラパラめくりながら後戻り
だいたい・・・で開いたり
パラパラめくったりを
機械的に処理してみましょう。
辞書は、1ページにたくさんの単語が載っていますが
単語1つを1データとします。
さらに、この辞書には1,024件のデータがあるとし、順に並んでいるとします。
調べる範囲は、最小値(1データ目)と最大値(1024)の間です。
①『music』が最小値より小さいか、最大値より大きい場合、この辞書には『music』が載っていないということになり、ここで終了とします。
②最小値と最大値の真ん中のデータを取り出します。
・データが『music』なら、ミッションコンプリート!で終了です。
・データが『music』より大きければ、
調べる範囲の最大値を真ん中のデータにして、①へ
・データが『music』より小さければ、
調べる範囲の最小値を真ん中のデータにして、①へ
終了するまで続けます。
もし、最初から順に調べるとしたら、最大で1,024回調べないといけませんが、
この方法なら、調べる範囲を1/2ずつ狭めていけるので、最大10回で結果が出ます。
これがバイナリーサーチ(二分探索法)です。
という話をしました
binary search なので、バイナリサーチ と表記されることが多いのですが
バイナ・リサーチではなく、バイナリ・サーチです。
【オンライン開催】
【8/11、8/13】愛される”心”のつくりかた基礎講座 Create A New Life