C++競プロ学習日記(仮)

( 学習記録であり解説Blogではないです )

二分法( 二分探索 )で平方根を求める

二分探索の練習をしました。
追記:二分探索と書いたけれど、正しくは二分法 *1 かも知れない...。
追記②:正しくは二分法だった...

整数 および 実数  x が与えられるので  y \ast y = x となるような y を絶対 or 相対誤差が 10^{-5} となる精度で求めてください。

#include <bits/stdc++.h>
using namespace std;
struct cww{cww(){ios::sync_with_stdio(false);cin.tie(0);}}star;
int main()
{
    int N;
    cin >> N;
    
    for( int i = 0; i < N; i++ )
    {
        double x;
        cin >> x;
        
        double left{}, right{ x }, mid{};
        
        if( x < 1 ) right = 1;
    
        while( right - left > 0.00001 )
        {
            mid = ( left + right ) / 2.0;
            if( mid * mid > x )
            {
                right = mid;
            }
            else
            {
                left = mid;
            }
        }
        cout << fixed << setprecision( 8 ) << mid << "  " << sqrt( x ) << endl;
    }
    return 0;
}

INPUT

5
2
4
0.5
0.1
10

OUTPUT

1.41420746  1.41421356
2.00000763  2.00000000
0.70709991  0.70710678
0.31623077  0.31622777
3.16227913  3.16227766

実行コードはこちら

  • x0 以下の場合の処理を忘れない。
  • while の loop 回数を 増やすと精度が上がって std::sqrt() *2 の結果に近くなる。


参考になる記事
satanic0258.hatenablog.com