はじめてのアドベントカレンダーAdvent Calendar 2024

二分探索法（バイナリサーチ）で問題解決力を高める：実生活への応用例

Posted at 2024-12-24

注意事項

本記事は最初に言いたいこと（まとめ）を書きました。
個人的に最後まで見ないと内容わからない記事は好きでないので、このような構成にしてます。

最初のまとめを読んで、役に立ちそうだなと思ったときは本記事を読んでもらえたら嬉しいです。

アルゴリズムやデータ構造など勉強すると必ずといっていいほど登場する二分探索法（バイナリサーチ）を問題の発生箇所特定に使ってない人がいることに知ったので本記事を作成しました。

===

硬い言葉でいうと、、、

二分探索法（バイナリサーチ：以下、バイナリサーチ）は、ソートされたデータから特定の値を効率的に探し出すアルゴリズム

です。
で後半に説明しますが、要は何かを探し出すときに使えるよ！ってことをこのあと説明していきます。

なお、バイナリサーチは以下のような手順にて目的の値を探し出す方法となります。

中央の要素を選択: データの中央に位置する要素を選びます
比較: 目的の値と中央の要素を比較します
- 目的の値が中央の要素より小さい場合、探索範囲を左半分に絞ります
- 目的の値が中央の要素より大きい場合、探索範囲を右半分に絞ります
再帰的操作: 上記の手順を、目的の値が見つかるか、探索範囲がなくなるまで繰り返します

例えば、以下のように昇順にソートされた数列があるとします：[3, 8, 14, 31, 55, 72, 98]

この数列から、値 72 を探すとなった場合、

初期設定:
- 左端（L）: インデックス 0（値 3）
- 右端（R）: インデックス 6（値 98）
1回目の比較:
- 中央（M）: インデックス 3（値 31）
- 72 は 31 より大きいため、探索範囲を右半分に絞ります
- 新しい左端（L）: インデックス 4（値 55）
2回目の比較:
- 中央（M）: インデックス 5（値 72）
- 72 は 72 と等しいため、目的の値が見つかりました

と2回で探し出すことができます。
一般的に、バイナリサーチは最大でも(log2N＋1)回、平均でもlog2N回という回数でできるため大規模になればなるほど効果的な探し方となります。

さて、ここからが本題です。
実生活での応用例として、システム障害が発生した時のことを考えてみます。

例えば「画面が表示されない」や「急に動作が重くなった」といった問題が発生した場合、バイナリサーチの考え方を応用すると以下のような手順になります。

手順:

システムの全体像を把握: システムが複数のモジュールやコンポーネントから構成されている場合、それらをリストアップし、依存関係やデータフローを確認します
問題の範囲を半分に分割: システム全体を大きく二つの部分に分け、どちらに問題が存在するかを確認します。例えば、フロントエンドとバックエンド、またはユーザーインターフェースとデータベースなどに分けます
各部分の検証:
- 片方の部分に問題がないことを確認できれば、もう片方に焦点を当てます
- 問題のある部分をさらに二つに分割し、同様の手順で問題箇所を絞り込んでいきます
詳細な調査:
- 問題のあるモジュールや機能が特定できたら、その内部をさらに細かく分割し、コードや設定、リソースの使用状況などを確認します
- ログやエラーメッセージを参照し、異常な動作やエラーの発生箇所を特定します

実際にはある程度の経験から問題の発生箇所をある程度推測してやることもありますが、正直良くわからんなーって時は変な先入観なく作業的に問題発生箇所特定できるので知っておくと便利なやり方かなと思います。

##参考文献##