二分探索の仕組み

二分探索は、並び替え済みの配列に対して使える探索方法です。探索範囲の中央の値と目標値を比較し、目標値の方が大きければ後半に、小さければ前半に探索範囲を絞ります。この絞り込みを繰り返すたびに探索範囲が半分になるので、線形探索よりずっと少ない回数で目標値を見つけられます。