LeetCode Sqrt(x)解題報告
http://oj.leetcode.com/problems/sqrtx/
つの整数の平方根を求めて、もし整数の平方根が整数でないならば、平方根を返して整理します.
最も簡単な方法は、暴力検索は1からN/2まで検索しますが、TLEができます.
二分サーチ、開始区間は1で、終了区間はxです.
ACコード:
つの整数の平方根を求めて、もし整数の平方根が整数でないならば、平方根を返して整理します.
最も簡単な方法は、暴力検索は1からN/2まで検索しますが、TLEができます.
二分サーチ、開始区間は1で、終了区間はxです.
ACコード:
public class Solution {
public int sqrt(int x) {
if(x<=1) {
return x;
}
int begin = 1;
int end = x;
int middle = 0;
while(begin<=end) {
middle = begin + (end - begin)/2;
// middle*middle==x，
if(middle==x/middle) {
return middle;
} else {
if (middle<x/middle) {
begin = middle + 1;
} else {
end = middle - 1;
}
}
}
// end <begin， end
return end;
}
}