はじめに
この記事は、信州大学ものづくりサークル「kstm」アドベントカレンダー2023の9日目として書かれました。
また厳密性のある技術的な話ではなく、どちらかというとネタ寄りです。
サークルの方が少しでも競技プログラミングに興味を持ってくれれば嬉しいです。
「右左どっち？」
突然ですが質問です！
あなたは 「右左どっち？」 と聞かれて何を思い浮かべますか？
TikTokやYouTube Shortsを見る人は、こんな光景を想像したのではないでしょうか。
あるいはそれを知らなければ、「どっちの手に入ってるかゲーム」を思い浮かべたかもしれません。
しかし競技プログラマーの僕は違います。
一体この図は何なのか、これから説明していきます。
二分探索とは
二分探索とは、単調性のあるデータ列に対して、中央の値と検索したい値の大小関係を比較することで、高速に検索したい値を探索するアルゴリズムのことです。
具体的に説明します。
今昇順にソートされているデータ列$[2, 3, 5, 7, 11, 13, 17, 19, 23]$があり、「13」という値を探したいとします。
初期状態では、中央の値は「11」で検索したい値は「13」ですので、中央の値から見て「右左どっち?」かというと右側にあります。
次に、探索する範囲を狭めます。「11」よりは右側にあることがわかったので、「11」より左側のデータは考えなくて良いです。つまり、データ列の左端を「11」として考えて良く、探索する範囲が狭まります。
同様に、新しいデータ列の中央の値は「17」で検索したい値は「13」ですので、「右左どっち？」にあるかというと左側にあります。
さらに探索する範囲を狭めます。「17」よりは左側にあることがわかったので、データ列の右端を「17」として考えることができます。
次に中央の値と検索したい値を比較すると、「13」で一致しました！
ここで探索終了です。
今回見たデータは、「11」と「17」と「13」なので、9個の要素を持つデータ列からわずか3回の探索で見つけることができました。
※N個の要素を持つソートされたデータ列から特定の値を検索したい場合、$[log_2 N]+1$回以下の探索で必ず見つかります。要素数が大きいほど効果的な探索ができます。
実用的なシーン
例えば、あなたは日記帳に1000日分の日記をつけていて、ある特定の日の日記を探したいとします。
もし二分探索の考えが思いつかず、前から1ページずつペラペラめくっていく場合（線形探索）では平均で500日、最悪1000日分の日付を読まないと見つかりません。
しかし二分探索を知っている場合、真ん中のページを開いて右か左かを繰り返して範囲を狭めていくと、10回ページを開くだけで必ず見つけられます！感動！！
おわりに
二分探索は分かりやすいながらも効果的な手法であるため、競技プログラミングでは入門的な立ち位置のアルゴリズムになっています。しかし一言で二分探索と言っても、「答えで二分探索」や「めぐる式二分探索」など幾つかの覚えるべき典型テクニックがあります。
競プロに浸かっていると、Shortsを見ていて不意に思い出すアルゴリズムがまだあります。来年のアドベントカレンダーでは 【31ゲーム】TikTokで思い出すアルゴリズム（動的計画法編） を書こうと思います。（修論に追われてなければ）
余談
個人的な話ですが、9月で緑色になり、また色々とキリの良いタイミングが重なったので一旦競プロから離れることにしました。
私はB4になってから始めましたが、就活のコーディングテストで足切りされなかったり、実装力に自信がついたので取り組んで良かったと思います。また、レートという数値で実力が可視化されるため、研究室の同期と毎週競って一喜一憂していたのも良い思い出になりました。
ただICPCにチャレンジできる最後の年で出場できなかったのが心残りで、もっと早くから始めておけば良かったと後悔しています。学部生の方で少しでも興味があれば、まずはコンテストに参加してみることをお勧めします！