九章アルゴリズム|Facebook面接問題:xに対してルートIIを開く

double sqrt(double x)およびx >= 0が実現される.
x開根後の値を計算して返します.
オンライン評価アドレス:LintCodeネクタイ
例1:

  : n = 2 
  : 1.41421356

例2:

  : n = 3
  : 1.73205081

【問題解】
アルゴリズム:二分
この問題には2つのやり方があります.1つはニュートン反復法で、1つは二分法です.ここでは二分法を紹介します.

二分浮動小数点数が通常の二分と異なるのはwhileの中でwhlie(left+eps

になったことである.

小数点以下の状況に注意し、x<1が右境界を1に拡大すると結果の誤り(例えば0.04=0.2*0.2)を避けることができるxの右境界を1に拡大しなければ、[0,0.04]の区間範囲内で正解

を見つけることができない.
複雑度分析

時間複雑度O(log(x))

二分の複雑さ

空間複雑度O(1)

余分なスペースを必要としない

public class Solution {
    /**
     * @param x: a double
     * @return: the square root of x
     */
    public double sqrt(double x) {
        double left = 0,right = x,mid;
        if (right < 1) {
            right = 1;
        }
        while (left + 1e-12 < right) {
            mid = left + (right - left) / 2;
            if (mid * mid < x) {
                left = mid;
            }
            else{
                right = mid;
            }
        }
        return left;
    }
}

詳細については、「9章アルゴリズム」を参照してください.