突然ですがクイズを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つに分けていくことを繰り返して確実に正解までたどり着きます。

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