二分法

binary search

参考

二分法の解説と、それを用いて平方根を求める手順が解説されている

例

二分法を用いて平方根を求めるプログラムをHaskellとRustで書いてみる

code:hs

c = 0.00000000001

f :: Double -> Double -> Double

f x n = x ^ 2 - n

calcSqrt :: Double -> Double -> Double -> Double

calcSqrt max min n | max - min < c = u

| f u n > 0 = calcSqrt u min n

| f u n < 0 = calcSqrt max u n

where

u = (max + min) / 2

sqrt' :: Double -> Double

sqrt' n = calcSqrt n 0 n

main = print $ sqrt' 2 -- 1.4142135623733338

code:rs

const C: f32 = 0.00001;

fn f(x: f32, n: f32) -> f32 {

x * x - n

}

fn sqrt(n: f32) -> f32 {

let mut max = n;

let mut min = 0.0;

loop {

let b = (max + min) / 2.0;

if f(b, n) < 0.0 {

min = b;

} else {

max = b;

}

if max - min < C {

return b

}

}

}

fn main() {

println!("{:?}", sqrt(2.0)); // 1.4142075

}

とあるインターンのコーディング課題で出た

その時はPythonで解いた