Write a method

boolean perfectSquare(int n) that returns true if n is a perfect square. You may not use Math.sqrt and the runtime must be O(logn).

Using this hint: Binary search to try to find a number whose square is n. Initialize low = 0 and high = n. Note that mid*mid may overflow, so you can avoid this by using a long.