---
tags: LeetCode
---

# 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    
Output: true    

Example 2:

Input: 14    
Output: false    

---
輸入範本如下

public class Solution {
    public bool IsPerfectSquare(int num) {
        
    }
}

### 直覺想法
[69. Sqrt(x)](https://hackmd.io/A_tG70spSzeXmPYAJXvcGg?view) 的變化題型

只要判斷是否有平方根就好.

1. 迴圈解

    36 ms	14.4 MB	
    You are here!
    Your runtime beats 92.86 % of csharp submissions.
    public bool IsPerfectSquare(int num)
    {
        int left = 0, right = num / 2 + 1;
        while (left <= right)
        {
            int mid = left + (right - left) / 2;
            long value = (long)mid * mid;
            if (value == num)
            {
                return true;
            }
            else if (value < num)
            {
                left = mid + 1;
            }
            else
            {
                right = mid - 1;
            }
        }
        return false;
    }

2. 遞迴解

    36 ms	14.5 MB
    You are here!
    Your runtime beats 92.86 % of csharp submissions.
    public bool IsPerfectSquare(int num)
    {
        return BinarySerach(0, num / 2 + 1, num);

        bool BinarySerach(int left, int right, int target)
        {
            if (left > right)
                return false;

            int mid = left + (right - left) / 2;
            long value = (long)mid * mid;
            return value == target ? true : 
                   value < target ? BinarySerach(mid + 1, right, target) : BinarySerach(left, mid - 1, target);
        }
    }

### Thank you!

You can find me on

- [GitHub](https://github.com/s0920832252)
- [Facebook](https://www.facebook.com/fourtune.chen)

若有謬誤 , 煩請告知 , 新手發帖請多包涵

# :100: :muscle: :tada: :sheep: