二分法

二分法 (<数学> 計算機の中でも実生活[辞書]でも使える)
基本的なアイディア
解(候補)集合を二つに分け、現時点の情報から解がどちらにあるか判定し選択する
解(候補)集合が十分に小く(要素が一つになるなど..)なれば、それを解とする
数値計算での二分法の適用
解の入っている区間[i,a]を二つに分ける [i,m], [m,a] (m=(a+i)/2)
「解の性質から、どちらに解があるかが解る」のであれば、二分法が適用できる
区間の幅(a-i)が十分に小く(先に定めたε以下に)なれば、解が(誤差ε以下で)得られる