二分探索

二分探索は、整列済み配列から目標値を探します。中央の要素を調べ、目標が存在しない側を除外して、残りの区間を半分にします。時間計算量は O(log n) で、百万要素でも最大二十回の探索で判定できます。

1 から 100 の数を当てるとき、50 より大きいと分かれば、1 から 50 を候補から外せます。二分探索も同じ仕組みです。配列が整列済みだからこそ、中央の値から未確認の半分について判断できます。

二分探索の仕組み

候補を閉区間 [lo, hi] で表します。初期値は lo = 0、hi = n − 1 です。各反復で mid = (lo + hi) // 2 を計算し、nums[mid] と target を比べます。

一致すれば mid を返します。nums[mid] < target なら、中央とその左側には目標がないため、lo = mid + 1 とします。nums[mid] > target なら中央と右側を除外し、hi = mid − 1 とします。

±1 は確認済みの中央を除外し、区間を縮めるために必要です。不変条件は「目標が存在するなら nums[lo..hi] に含まれる」です。lo > hi で区間が空になれば、目標は存在しないので −1 を返します。

二分探索のステップ

初期入力は nums = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]、目標は target = 23 です。

1. lo = 0、hi = 9 から mid = 4 を得ます。nums[4] = 16 < 23 なので、添字 0–4 を除外し、lo = 5 にします。
2. lo = 5、hi = 9 から mid = 7 を得ます。nums[7] = 56 > 23 なので、添字 7–9 を除外し、hi = 6 にします。
3. lo = 5、hi = 6 から mid = 5 を得ます。nums[5] = 23 と一致し、添字 5 を返します。

十要素のうち、調べた位置は三つです。目標が 24 なら、次に添字 6 の 38 を調べて hi = 5 にします。lo = 6 > hi となるため、結果は −1 です。

アニメーションの左右の境界は候補区間、mid は今回調べる位置を示します。区間外のセルが薄くなるのは、その位置を候補から除外できた印です。一致したセルは緑になります。

時間・空間計算量

候補数は一回ごとにほぼ半分になります。データ量が二倍になっても、必要な探索は約一回増えるだけです。百万要素なら最大二十回、十億要素なら最大三十回です。反復実装は境界と中央の添字だけを保持し、追加領域は O(1) です。

境界条件

• 空配列：hi = −1 なので、最初から lo <= hi が偽になります。要素を調べず −1 を返します。
• 一要素：lo = hi = 0 で、一回の確認で決まります。
• 先頭・末尾の目標：区間を端へ絞り込みます。約 log n 回かかる場合があります。
• 隣接する値の間にある目標：最後の候補も一致せず、境界が交差して −1 を返します。
• 重複値：通常の二分探索は一致する位置のどれかを返します。最初・最後の位置を求めるには、bisect_left、bisect_right などの変種を使います。

よくある間違い

• lo = mid にする：境界が隣り合うと中央は lo に切り下げられ、区間が変わらずループが終わりません。プレイヤーの lo = mid 変種で確認できます。
• lo < hi にする：閉区間の最後の一要素を調べずに終了します。この変種で最小値を探すと、存在する値を見落とします。
• 中央の計算でオーバーフローする：Java や C++ の固定幅整数では lo + hi が範囲を超える場合があります。lo + (hi - lo) / 2 を使います。表示される Python コードは任意精度整数を使います。
• 未整列の入力を使う：半分を除外する根拠がなくなり、目標を見落とす場合があります。整列済みであることが前提です。
• 存在確認にも常に二分探索を使う：ハッシュ集合の検索は平均 O(1) です。二分探索は整列済みデータ上の位置、挿入位置、近隣値を求める処理に適しています。