isPerfectSquare.h

//
//  isPerfectSquare.h
//  bsearch
//
//  Created by junl on 2019/7/19.
//  Copyright © 2019 junl. All rights reserved.
//

#ifndef isPerfectSquare_hpp
#define isPerfectSquare_hpp

#include <stdio.h>
/*
 367.给定一个正整数 num，编写一个函数，如果 num 是一个完全平方数，则返回 True，否则返回 False。
 
 说明：不要使用任何内置的库函数，如  sqrt。
 
 示例 1：
 
 输入：16
 输出：True
 示例 2：
 
 输入：14
 输出：False
 
 来源：力扣（LeetCode）
 链接：https://leetcode-cn.com/problems/valid-perfect-square
 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */

bool isPerfectSquare(int num) {
    if (num<=1) return true;
    int left=1;
    int right=num/2;
    while (left<right) {
        int mid = left + (right-left)/2;
        if (mid>=num/mid) {
            //至少mid^2大于num
            right=mid;
        } else {
            //mid^2无限逼近num
            left=mid+1;
        }
    }
    return (long)left*left == num;
}

#endif /* isPerfectSquare_hpp */