二分探索の境界条件とオフバイワンエラーの注意点
二分探索の境界条件とオフバイワンエラーの注意点は、探索範囲を中央の比較で半分ずつ捨てる探索法である。
仕組み
整列済み列で中央値と目的値を比較し、小さければ左半分、大きければ右半分へ境界を更新する。
計算量・性質
反復回数は高々⌈log2(n+1)⌉程度で時間O(log n)、反復実装の補助領域O(1)。
具体例
[2,5,8,12,16]から12を探すと8より右、次の12で発見する。
限界と注意点
未整列データには使えず、境界更新と中央計算のoff-by-oneに注意する。