public class Solution {
public boolean isPerfectSquare(int num) {
if(num == 1)
return true;
long low = 1,
high = num / 2,
mid = 0;
long nums = (long)num;
while(low <= high)
{
mid = low + (high  low) / 2;
if((mid * mid) == nums)
return true;
else if( (mid * mid) < nums)
low = mid + 1;
else
high = mid  1;
}
return false;
}
}
Java Binary Search Solution ( the obvious one)


@hualiang2 , in the problem statement , it is written as "Given a
positive
integer num" ,
and 0 is neither positive nor negative . Even OJ's expected output returns false.Yes, if you consider real world scenario, then the function should return true (which I can amend accordingly).

@MichaelWayne , in test cases like 808201, when we calculate
mid
value , it comes out to be404101
. So, when we domid*mid
, it goes completely out of int range, hence I used long datatype.


@jjung Yes and the reason is to avoid integer overflow. (Although overflow will happen if the integers are very large).

@jjung You can try to do this problem "Guess Number" and you will understand why we did this.

@MichaelWayne The tricky part is that the JAVA won't promote the int to a long on its own since we are multiplying two integers and a resulting integer will already overflow. So the multiplication needs to be using either both longs or atleast one long in the cast.
