アルゴリズム図鑑
二分探索
小さい順に並んだ配列で、真ん中の値と比べて探す範囲を半分ずつ狭めていく方法です。
考え方
- データが整列済みであることが前提
- 真ん中の値より大きければ右半分、小さければ左半分だけを探す
- 1回比べるごとに範囲が半分になるので、計算量は O(log n)
試験でのポイント
- mid ← (low + high) ÷ 2 の「÷」は商（小数点以下を切り捨てた値）として扱う
- low ← mid + 1 と high ← mid - 1 の「+1」「-1」を忘れると、同じ範囲を探し続けて終わらなくなる
関連する用語二分探索オーダ記法配列