【第55話】ただの友達、なの？｜ITパスポート 令和5年度 問69

登場人物

美咲（みさき）

女子大生。就活のエントリーシートの資格欄が真っ白なことに気づき、慌ててITパスポートの勉強を開始。ITは完全に素人。高校時代は可愛くて人気者だったので、ちょっとプライドが高い。素直じゃない。

拓也（たくや）

美咲の高校時代の同級生。東京大学工学部。子どもの頃からパソコンばかりいじってきた生粋のオタク。実は美咲のことが好きだが、10年近く言い出せていない。教えるのは得意だが、口が悪いのが玉に瑕。

今日の問題

第1幕：研究室という、初めての場所

10月、研究室配属になった拓也から、初めて「今度、うちの研究室に来る?」と誘われた。美咲は少し緊張しながら、大学構内の古い建物の一室に足を踏み入れる。

美咲

……ここが、あんたの研究室

拓也

散らかっててごめん。奥の棚、論文集がぎっしり詰まっててさ

書棚には、背表紙に整理番号が振られた分厚い論文集が何十冊も並んでいた。サーバーラックが低く唸り、機材の合間に先輩たちの私物のマグカップが転がっている。

美咲

なんか、思ってたより雑然としてるのね

拓也

そこは否定できない。あ、そうだ、今日の問題、ちょうどこの棚を見てて思いついたんだ

第2幕：2分探索のほうが絶対速いでしょ

奥の作業スペースで、拓也がノートパソコンを開く。

美咲

じゃあ答えるわね。これエでしょ。『2分探索法のほうが、探索する値によらず常に計算量が少ない』

拓也

お、なんでそう思った?

美咲

だって、2分探索って半分ずつ絞り込んでいくんでしょ? 　だったら、いちいち端から数える線形探索より、どんな場合でも絶対速いはずじゃない

拓也

発想はすごく筋がいいんだけど、実は"だいたい速い"のと"どんな場合でも必ず速い"は、微妙に違うんだ

美咲

え、違うの?

拓也

うん。今日の問題が聞いてるのは、実は2分探索と線形探索の比較じゃなくて、"線形探索そのものの性質"なんだ

第3幕：端からめくるか、真ん中から開くか

拓也は棚から分厚い論文集を1冊抜き出した。

拓也

たとえば、この論文集の中から、ある1本の論文を探すとするよね。方法は2つある

美咲

うん

拓也

1つ目は、表紙から順に、1ページずつめくって探す方法。これが線形探索。もう1つは、まず真ん中あたりを開いて、探してる論文がそれより前か後ろかで半分に絞り、また真ん中を開く……を繰り返す方法。これが2分探索

美咲

あ、それはわかるわ。真ん中から絞ったほうが、圧倒的に早く終わりそうよね

拓也

その通り。だから2分探索のほうが"平均すると"速いのは正しい。でも、線形探索そのものにも、はっきりした性質があるんだ。"探す論文が多ければ多いほど、端からめくる手間もその分だけ増える"。つまり、線形探索に必要な計算量は、配列の要素数にそのまま比例するんだ

美咲

あ……! 　それって、イのことね

拓也

そのとおり。正解はイ。線形探索は、要素数が2倍になれば、最悪の場合の手間も2倍になる。この"比例する"って性質を、今日の問題は聞いてるんだ

第4幕：た、ただの友達です

説明が一段落したところで、研究室のドアが開いた。先輩が「あれ、拓也くん、今日は珍しく研究室にいるじゃん」と声をかけながら入ってきて、美咲に気づき、にやりと笑った。

「あー、これが噂の子?」と先輩が冷やかすように言った。

拓也は一瞬固まったあと、早口で「た、ただの友達です」と言い切った。

その場に、変な間ができた。

美咲

……そう。ただの友達、なんだ

拓也

あ、いや、今のは、その

美咲

別に、いいけど。事実だし

美咲は特に怒った様子も見せず、ノートに視線を戻した。ただ、さっきまでより少しだけ、声のトーンが低くなっていた。

先輩は空気を読んだのか、「お邪魔しました」とそそくさと出ていった。

拓也

……美咲、あの

美咲

気にしてないから、続き教えて

拓也

（……しまった。なんで、あんな反射的に）

第5幕：残りの選択肢を片付ける

気まずさを引きずったまま、拓也はノートに向き直る。

美咲

……気を取り直して。残りのアとウも教えて

拓也

アの『2分探索法は、先頭から順に探索する』は、さっき説明した線形探索の動き方そのもの。2分探索と線形探索の説明が、丸ごと入れ替わってるパターンなんだ

美咲

じゃあウは?

拓也

ウの『線形探索法にはソートが必要』も、これも入れ替わってる。ソートが必須なのは2分探索のほう。真ん中で大小を比較して絞り込む都合上、事前に順番が揃ってないと成立しないんだ。線形探索は端から全部見るだけだから、ソートされてなくても関係なく使える

美咲

線形探索は端から全部、ソート不要。2分探索は真ん中から絞る、ソート必須。……アとウ、丸ごと入れ替えて出題してたのね

拓也

完璧な整理。この手の問題は、"2つの手法の説明を、そのまま入れ替えて出す"パターンがすごく多いから、片方だけじゃなく両方セットで覚えておくと引っかからないよ

まとめ：選択肢ごとの答え合わせ

答えイ　線形探索法の計算量は要素数に比例する

覚え方のコツ

端から全部めくるのが線形探索、真ん中から絞るのが2分探索。

• 線形探索＝配列の先頭から順に調べる方法。ソート不要。計算量は要素数に比例する
• 2分探索＝中央の要素と比較しながら範囲を半分ずつ絞り込む方法。事前のソートが必須
• 「探索する値によらず必ず2分探索が速い」は誤り。探す値が先頭近くにあれば、線形探索が一発で終わることもある

エピローグ

先輩が完全に帰ったのを見計らって、美咲がノートを閉じた。

美咲

今日はいろいろ、新しいもの見られたわね。あんたの研究室も、"ただの友達"の扱いも

拓也

……まだ言う?

美咲

言うわよ。だって、あんな即答されると思わなかったし

拓也

いや、あれは、先輩が急に変なこと言うから、反射的に

美咲

反射的に出てくる答えが、それってことでしょ

拓也心の声

……違う。反射的に出てきたのは、否定する言葉のほうで、本当は全然違う

拓也

……ごめん

美咲

別に、謝られるようなことでもないけど

美咲はそう言って、少しだけ気まずそうに視線を逸らした。

美咲

……次、来るときは、ちゃんと紹介しなさいよね。"ただの"、じゃなくて

拓也

……善処します

拓也心の声

……次があるのか。それだけで、今日は十分だ

研究室の窓の外は、もう夕方の色に染まっていた。サーバーの唸る音だけが、静かに続いていた。

今日のポイントおさらい

1. 線形探索法＝配列の先頭から順に調べる方法。計算量は要素数に比例する
2. 2分探索法は、中央の要素と比較しながら範囲を半分ずつ絞り込む方法
3. 2分探索法を使うには、配列が事前にソートされている必要がある（線形探索は不要）
4. 「2分探索は探索する値によらず必ず速い」は誤り。探す値の位置次第では線形探索が一発で終わることもある
5. 探索アルゴリズムの問題は、2つの手法の説明が丸ごと入れ替わっているパターンが多いので、両方セットで覚えると引っかからない

この記事はITパスポート試験 令和5年度 問69（テクノロジ系／アルゴリズム）の解説です。