141 · Sqrt(x) - LintCode

# Description

Implement int sqrt(int x) .

Compute and return the square root of x.

# Example

Example 1:
	Input:  0
	Output: 0


Example 2:
	Input:  3
	Output: 1
	
	Explanation:
	return the largest integer y that y*y <= x. 
	
Example 3:
	Input:  4
	Output: 2

# Challenge

O(log(x))

# Code

可以用數學解

	class Solution {
	public int mySqrt(int x) {
	if (x == 0) {
	return 0;
	}
	int ans = (int) Math.exp(0.5 * Math.log(x));
	return (long) (ans + 1) * (ans + 1) <= x ? ans + 1 : ans;
	}
	}

用二分法
1. 要注意的是如果設 mid * mid == x 很有可能會溢出，有可能需要用 long / BigInteger 類型；題如果使 mid == x /mid 就不用轉了

	public class Solution {
	/**
	* @param x: An integer
	* @return: The sqrt of x
	*/
	public int sqrt(int x) {
	if (x <= 1) return x;
	int start = 1, end = x;
	while (start + 1 < end) {
	int mid = start + (end - start) / 2;
	if (mid == x / mid) return mid;
	if (mid < x / mid) {
	start = mid;
	} else if (mid > x / mid) {
	end = mid;
	}

	}

	if (end <= x / end) return end;
	return start;
	}
	}