🔍 Binary Search Algorithm - 詳細解析
計算量分析
時間計算量: O(log n) - 各ステップで検索範囲を半分に削減
空間計算量: O(1) - 定数の追加メモリのみ使用
1. 初期化
left = 0
right = n-1
2. 中点計算
mid = left + ⌊(right-left)/2⌋
3. 比較
nums[mid] と target を比較
4. 範囲更新
条件に応じて left または right を更新
📊 実例による段階的解析
🎯 アルゴリズムの核心理解
なぜ O(log n) なのか？
各ステップで検索範囲を半分に削減するため、最大でも log₂(n)
回の比較で完了します。 例: n=1000の場合、最大10回の比較で結果が得られます。
挿入位置の判定
ターゲットが見つからない場合、leftポインターが自然に正しい挿入位置を指します。
これは、leftが常に「ターゲット以上の最小要素の位置」を維持するためです。