May Leetcode Challenge - Day 9

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

Solution

x * x = num, so just iterate from 1 to x
An optimize solution, with O(logn) time, is use middle of 1 and num
if middle * middle > num, repeat process for 1 to middle
if middle * middle < num, repeat process for middle to num

class Solution {
    func isPerfectSquare(_ num: Int) -> Bool {
        if num == 1 { return true }
        
        var lower = 1
        var middle = (num + lower) / 2
        
        while lower < middle {
            let square = middle * middle
            if square == num { 
                return true
            }
            if square < num {
                lower = middle
                middle = (num + lower) / 2
            }else{
                middle = (middle + lower) / 2
            }
        }
        
        return false
    }
}