问题描述
Implement int sqrt(int x).
Compute and return the square root of x, where x is guaranteed to be a non-negative integer.
Since the return type is an integer, the decimal digits are truncated and only the integer part of the result is returned.
Example 1:
Input: 4 Output: 2 Example 2:
Input: 8 Output: 2 Explanation: The square root of 8 is 2.82842…, and since the decimal part is truncated, 2 is returned.
解决思路
思路就是a^2中，a一定小于a^2/2 - 1,然后设置头指针，和尾指针，不断的用二分法来找到a
代码
package leetcode;
public class Sqrt {
public int mySqrt(int x) {
if (x <= 0) return 0;
long start = 1;
long end = x/2 + 1;
long mid = 1;
while (start <= end){
mid = (start + end) / 2;
long temp = mid * mid;
if (temp == x) return (int)mid;
else if (temp < x) start = mid + 1;
else if (temp > x)end = mid - 1;
}
return (int)end;
}
}
