Overview
Binary Search は sorted array を半分ずつ絞って target を探します。
Analogy
辞書で単語を探すときのように、真ん中を見て左か右を選びます。
Step-by-step
- low = 0, high = n - 1 で開始。
- mid = (low + high) // 2 を計算。
- arr[mid] == target なら mid を返す。
- target が小さければ high = mid - 1。
- それ以外は low = mid + 1。low <= high の間繰り返す。
Visual
[1 3 5 7 9] -> 5 を確認 -> 右へ -> 7 を発見。
Common mistakes
- low/high 更新後に mid を再計算しない。
- ループ条件を < にして最後の要素を見落とす。
- mid = (low + high) は言語によって overflow する可能性。
Practice questions
- 7 要素の配列で存在/未存在 target をトレースする。
- 見つからない場合に insertion index を返す版を作る。
- なぜ sorted が必須かを反例で説明する。