二分法とは？

二分法の意味

解を含むことが分かっている区間の中点を取り、解がどちら側にあるかを判定して区間を半分に狭める操作を繰り返す求解法。1回ごとに区間幅がちょうど半分になる。

二分法の具体例

区間幅1から始めて誤差0.001未満にしたい場合、1/2のn乗＜0.001となる最小のnは、2の10乗＝1024＞1000より10回。

二分法は試験でどう引っ掛けられる？

反復回数は「精度の逆数」ではなく「幅が半減する回数」で決まる。log2で考える。

二分法と関連する用語

• ニュートン法
• 2分探索木

二分法が出た過去問

• 0≦x≦1の範囲で単調に増加する連続関数f(x)がf(0)＜0≦f(1)を満たすときに、区間内でf(x)＝0であるxの値を近似的に求めるアルゴリズムにおいて、(…

  正解：10

  要点：二分法の反復回数は幅が半減する回数で決まる

  これは区間を半分ずつ狭めていく二分法である。中点を取るたびに残り幅は半減し、n回目の中点計算の直後にはx1－xが1/2のn乗となる。終了条件1/2のn乗＜0.001を満たす最小のnは、2の10乗＝1024＞1000より10回である。

  出典：平成28年度 秋期 高度共通_午前I試験 am1 問1（IPA）

• 0≦x≦1の範囲で単調に増加する連続関数f(x)がf(0)<0≦f(1)を満たすときに、区間内でf(x)=0であるxの値を近似的に求めるアルゴリズムにおいて、(…

  正解：10

  要点：二分法の反復回数は1/2のk乗が精度を下回るkで決まる

  これは区間を半分ずつ狭める二分法である。(2)をk回目に実行した直後の区間の半分の幅はx1−x＝1/2のk乗となる。終了条件1/2のk乗＜0.001を満たす最小のkは、2の10乗＝1,024＞1,000より10である。したがって(2)は10回実行される。

  出典：令和7年度 春期 高度共通_午前I試験 am1 問1（IPA）