以下では、TypeScript で書かれた「方程式
この方程式のグラフは次のような 単調増加関数です。
^
y | ●← y = x^3 + x
| ●
| ●
| ●
| ●
| ●
+-----------------------------→ x
- x が増えると f(x) も増える（単調増加） ➜ 二分探索が使える！
const input: string = fs.readFileSync('/dev/stdin', 'utf8').trim();
const N: number = parseFloat(input);- ユーザーが入力した
$N$ を文字列として受け取り、数値に変換します。 - 例：
"2"→2
標準入力: "2" ──→ parseFloat ──→ N = 2
let low: number = 0.0;
let high: number = Math.max(1.0, N);探索範囲:
low = 0.0
high = N（例: 2.0）
なぜ
high = max(1.0, N)？
- N が 1 未満のときでも解は 0〜1 にあるので安全に解が含まれるようにしている。
for (let i = 0; i < 100; i++) {
mid = (low + high) / 2;
const fx = mid ** 3 + mid;
if (fx > N) {
high = mid;
} else {
low = mid;
}
}ステップ1：
low = 0.0
high = 2.0
mid = 1.0
f(1.0) = 1 + 1 = 2 → 合ってる！収束開始！
ステップ2：
low = 0.0
high = 1.0
mid = 0.5
f(0.5) = 0.125 + 0.5 = 0.625 → 小さい → low を上げる！
ステップ3：
low = 0.5
high = 1.0
mid = 0.75
f(0.75) = 約1.172 → まだ小さい → low を上げる！
ステップn：
...
- 二分探索により区間幅は次のように縮小：
最初: [0.0 ................................................... 2.0]
↓
次回: [0.0 ......................... 1.0]
↓
さらに: [0.5 ............... 1.0]
↓
最終的に: [0.99999 .. 1.00001]
console.log(mid.toFixed(6));- 絶対誤差または相対誤差が 0.001 以下になる精度で出力（6桁指定）。
結果: mid = 1.000000
▼ 入力
┌─────────────┐
│ N（整数） │ ← 標準入力 fs
└────┬────────┘
│
▼
▼ 二分探索の初期化
┌─────────────┐
│ low = 0 │
│ high = N │
└────┬────────┘
│
▼
▼ 反復探索（精度 0.001）
┌─────────────┐
│ mid = (low + high) / 2 │
│ f(mid) = mid³ + mid │
│ fx > N → high = mid │
│ fx < N → low = mid │
└────┬────────┘
│（100回繰り返す）
▼
▼ 結果出力
┌─────────────┐
│ mid.toFixed(6) │ → 絶対誤差・相対誤差0.001以下
└─────────────┘
-
毎回探索範囲を 1/2 に狭める ⇒ 誤差
$\leq 10^{-6}$ になるには：$$ 2^{-n} \leq 10^{-6} ⇒ n ≈ 20 $$
-
つまり 20〜30回でも十分。100回は安全マージン。