# O(logN) Bisection method

• ``````bool isPerfectSquare(int num) {
long long l = 0, r = num;
while (l <= r) {
long long mid = (l + r) >> 1;
long long sqmid = mid * mid;
if (sqmid > num) r = mid - 1;
else if (sqmid < num) l = mid + 1;
else return true;
}
return false;
}``````

• I have a very similar answer. One trick, instead of using long long to prevent overflow, you can check to see if mid * mid == target => mid == target / mid, which won't overflow.

• mid == target / mid and meanwhile target % mid == 0.
thank you~

• ``````public boolean isPerfectSquare(int num){

if(num <= 0) return false;

int left = 1, right = num;

while(left <= right){
int mid = left + (right - left)/2;
//用除法可以避免溢出
if(mid > num / mid){
right = mid - 1;
}else if(mid < num / mid){
left = mid + 1;
}else{
return num % mid == 0;
}
}
return false;
}
``````

• Golang solution:

``````func isPerfectSquare(num int) bool {
if num == 1 {
return true
}
l := 1
r := num
for l < r {
mid:= l + (r - l) / 2
a := int(math.Pow(float64(mid), 2))
if a == num {
return true
} else if a < num {
l = mid + 1
} else {
r = mid - 1
}
}
return int(math.Pow(float64(l), 2)) == num
}
``````

• @noobsky If you set the initialized maxValue to (int)Math.sqrt(Integer.MAX_VALUE),you will not get overflow problem because (int)Math.sqrt(Integer.MAX_VALUE) * (int)Math.sqrt(Integer.MAX_VALUE) must less than or equal Integer.MAX_VALUE.To core code,using this method will not violate the regulations of this work.

• @noobsky You are a chinese,me too,haha.

• @ShuangquanLi why target%mid==0 and how long long solve this problem?

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.