兩道用到二分法的math題：Sqrt(x) && Pow(x, n)

第一題求一個int數的平方根，傳回值也是int，開始直接用循環做，結果不出意料的逾時了，還是要用二分法。

每一次都排除掉一半的值，時間複雜度就低了很多~

代碼的實作還是很簡單易懂的：

public int sqrt(int x) {
        int low = 0;
		int high = x;
		double diff = 0.01;
		while(low <= high){
			double mid = (high+low)/2;
			if((x-mid*mid)>diff){
				low = (int)mid+1;
			}else if((x-mid*mid)<-diff){
				high = (int)mid-1;
			}else if((x-mid*mid)>=-diff && (x-mid*mid)<=diff){
				return (int)mid;
			}
		}
		return high;
    }
           

第二題求幂，做法更簡單，不過得考慮奇偶數和正負數幂，其他沒什麼特别的。

public double pow(double x, int n) {
		if(n>0)
			return power(x,n);
		else
			return 1/power(x,-n);
    }
	public double power(double x, int n){
		if(n == 0)return 1;
		
		double v = power(x,n/2);
		
		if(n%2 == 0)
			return v*v;
		else
			return v*v*x;
	}