二分探索
配列中央の値を見て、探索したい値より大きければ配列の左半分に、小さければ配列の右半分に探索範囲を絞る
以下繰り返し
配列の要素数$ Nに対して$ \mathcal{O}(\log_2N)
初期条件
high = 最大値 + 1
low = 最小値 - 1
境界に余裕をもたせておくことで、終了時までhigh(またはlow)が一定だったとしても、最大値(または最小値)ピッタリまで探索されることを保証できる
終了条件
high - low > 1を満たさなくなったら終了
2点の区間まで絞られた後、区間が変わらないことがあるが、中間点は常にmid = (high + low) / 2 = lowであり探索点がそれ以上変化しない
探索結果