package org.enricogiurin.codingchallenges.leetcode.challenge052020;

public class ValidPerfectSquare {

    public boolean isPerfectSquare(int num) {
        if (num < 1) {
            return false;
        }
        if (num == 1) {
            return true;
        }
        return search(1, num / 2, num);
    }

    private boolean search(long low, long high, int square) {
        if (high < 1 || low > high) {
            return false;
        }
        long pivot = low + (high - low) / 2;
        long candidateSquared = pivot * pivot;
        if (candidateSquared == square) {
            return true;
        }
        if (candidateSquared > square) {
            return search(low, pivot - 1, square);
        } else {
            return search(pivot + 1, high, square);
        }
    }


    public static void main(String[] args) {
        ValidPerfectSquare instance = new ValidPerfectSquare();
        //boolean result = instance.isPerfectSquare(808201);
        boolean result = instance.isPerfectSquare(2);
        System.out.println(result);
    }
}
