0≦x≦1の範囲で単調に増加する連続関数f(x)がf(0)<0≦f(1)を満たすときに，区間内でf(x)=0であるxの値を近似的に求めるアルゴリズムにおいて，(2)は何回実行されるか。
〔アルゴリズム〕
(1) x_0←0，x_1←1とする。
(2) x←(x_0+x_1)/2とする。
(3) x_1−x＜0.001ならばxの値を近似値として終了する。
(4) f(x)≧0ならばx_1←xとして，そうでなければx_0←xとする。
(5) (2)に戻る。
正答1
解説
正解は1です。
区間を半分ずつに絞り込んで解を求める二分法（バイセクション法）で、終了までの反復回数を求める問題です。
(2)で区間の中点xを求め、(3)で「x_1−x」すなわち区間幅の半分が0.001未満かを判定します。
(4)で解を含む側の半分の区間を残すので、区間幅は1回ごとに半分になります。
【計算】
i回目に(2)を実行する時点の区間幅は(1/2)^(i−1)です。
このときx_1−xは区間幅の半分なので、(1/2)^iになります。
終了条件は(1/2)^i＜0.001、つまり2^i＞1,000です。
2^9＝512は1,000以下なので、9回目では終了しません。
2^10＝1,024は1,000を超えるので、10回目の(3)で終了します。
よって、(2)は10回実行されます。
【選択肢別解説】
1：○ 上の計算のとおり、x_1−xが0.001未満になるのは10回目です。
(2)はその直前に毎回1度ずつ実行されるので、実行回数は10回です。
2：× 20回目まで続くのは、区間幅が1回ごとに半分ではなく、もっとゆっくり縮む場合です。
二分法では10回で幅の半分が1/1,024になり、条件を満たします。
3：× 100回は、区間幅が毎回0.01ずつ減るような線形の絞り込みを想定した値です。
実際は毎回半分になるため、はるかに少ない回数で終わります。
4：× 1,000回は、0.001刻みで区間を順に調べる場合の回数です。
二分法は区間を指数的に縮めるので、このような回数にはなりません。
【ポイント】
二分法ではn回の反復で区間幅が1/2^nになります。
精度0.001なら2^10＝1,024がおよそ1,000であることから、約10回と見当を付けられます。