求平方根.md

求平方根

二分查找：

因为查找的过程中是线性增加的，所以应该想到二分。判断左右节点之差是否小于 diff，接着继续二分左右节点之和，再根据其平方是否大于给定数移动左节点或右节点。

package src.Algorithm;

public class SquareRoot {

    public static double squareRoot(int num){
        double diff = 1e-9;
        double left = 1.0, right = num * 1.0;
        while(right - left > diff){
            double mid = (right + left) / 2.0;
            if(mid * mid > num){
                right = mid;
            } else {
                left = mid;
            }
        }
        String s = left + "";
        return Double.parseDouble(s.substring(0, 11));
    }

    public static void main(String[] args) {
        System.out.println(squareRoot(3));
    }
}

Go 语言：

package main

import "fmt"

func main() {
	num := 8
	target, left, right := float64(num), float64(0), float64(num)
	for right-left > 1e-7 {
		mid := (left + right) / 2
		if mid*mid > target {
			right = mid
		} else {
			left = mid
		}
	}
	fmt.Println(left)
	fmt.Println(right)
}