367. Valid Perfect Square

Given a positive integer num, write a function which returns True if num is a perfect square else False.

Note: Do not use any built-in library function such as sqrt.

Example 1:

Input: 16

Returns: True

Solution 1: use BST,O(logn)

 1 class Solution {
 2 public:
 3     bool isPerfectSquare(int num) {
 4         if (num==1) return true;
 5         int begin=0,end=num;
 6         while (begin<end-1){
 7             long long mid=(begin+end)/2;
 8             if (mid*mid==num) return true;
 9             if (mid*mid<num) begin=mid;
10             if (mid*mid>num) end=mid;
11         } 
12         return false;
13     }
14 };

Solution 2: Newton's method, http://blog.csdn.net/wangxiaojun911/article/details/18203333

1 class Solution {
2 public:
3     bool isPerfectSquare(int num) {
4         long long x=num;
5         while(x*x>num) x=(x+num/x)/2;
6         return x*x==num;
7     }
8 };

Soulution 3: q_math.c special method, O(1)