突然ですがクイズを1つ。

これはIT企業の入社面接で使われたことのある問いです。ある「解法」を知っていれば簡単に解ける問いで，面接官はその「解法」を知っているかどうかを尋ねています。

「解法」は，正確にいえば「アルゴリズム」となります。この面接官が聞いているのは，ごく基本的なアルゴリズムを知っているかどうか，ということです。

アルゴリズム。たまに目にしたりすることがある言葉と思いますが，その意味をご存じでしょうか？

アルゴリズムは，一言で表すのは難しい言葉です。新刊『アルゴリズム はじめの一歩 完全攻略』の冒頭では，次のように説明されています。

筆者の手元にある『新英和中辞典』（⁠研究社）では，algorithmという英語を，以下の日本語に訳しています。これらは，どれも「与えられた問題の解を得る方法」という意味です。

英和辞典の和訳

→「⁠演算法」「⁠演算方式」「⁠算法」

インターネットのgoo辞書によると，algorithmの語源は，9世紀の数学者の名前が著作を通して学術用語となった，「⁠数」を連想させるもの，となっています。

語源

→数学者の名前，数を連想させるもの

日本工業規格のJIS X 0001：1994「情報処理用語−基本用語」では，アルゴリズムという用語を，以下のように定義しています。

JISの定義

→「⁠問題を解くためのものであって，明確に定義され，順序付けられた有限個の規則からなる集合」

これらをまとめると，アルゴリズムは，「⁠数」に関する「問題を解く方法」だということになります。そして，コンピュータの分野では，「⁠明確であること（あやふやな部分がないこと⁠）⁠」と「有限であること（いつ終わるかわからない手順でないこと⁠）⁠」という条件が付きます。

冒頭のクイズは，このアルゴリズムにのっとって正解を導けます。たとえば面接官の頭の中にある数字が「3」だったとします。

• 受験者：1～100の真ん中の値である「50（もしくは51⁠）⁠」と答える
• 面接官：「もっと小さい」と答える
• 受験者：1～49の真ん中の値である「25」と答える
• 面接官：「もっと小さい」と答える
• 受験者：1～24の真ん中の値である「12（もしくは13⁠）⁠」と答える
• 面接官：「もっと小さい」と答える
• 受験者：1～11の真ん中の値である「6」と答える
• 面接官：「もっと小さい」と答える
• 受験者：1～5の真ん中の値である「3」と答える

数が偶数個の場合はぴったり真ん中になる値（中央値）はないので，「⁠50（もしくは51⁠）⁠」などとしていますが，奇数個ならぴったり真ん中の数が見つかります。このように，全体から範囲を徐々に絞りつつ探索していくことを「二分探索」といいます。基本的なアルゴリズムの1つです。

1～100→1～49→1～24→1～11→1～5と，正解に向かって網を狭めていきます。もっと具体的にいえば，中央値50より小さいということは，1～49の中に正解がある（51～100に正解はない⁠）⁠→中央値25より小さいということは，1～24の中に正解がある（26～49に正解はない⁠）⁠→中央値12より小さいということは，1～11の中に正解がある（13～24に正解はない）……となり，正解の可能性があるグループと不正解のグループの2つに分けていくことを繰り返して確実に正解までたどり着きます。

「アルゴリズム」にぴったりはまる訳語はないため，「⁠問題を解くためのものであって，明確に定義され，順序付けられた有限個の規則からなる集合」といったお堅い説明になってしまうのですが，簡単な具体例を通して見てみると「そういうことか」と納得いただけるのではないでしょうか。