(0) Binary Search: Valid Perfect Square

Question Link and Solution Link

Difficulty: Easy

Problem Statement: Given positive number return true if the number is perfect square else return false.

Approach1: Use a simple while loop and traverse through all numbers starting from 1 (cur) and check if cur*cur == num. If at any point it's true then return true else after the loop returns false.

bool isPerfectSquare(int num)
{
    long long cur = 1;
    while (cur * cur <= num)
    {
        if (cur * cur == num) return true;
        cur++;
    }
    return false;
}

Approach2: Use binary search. Make low=1 and high=2^31-1 because our lowest value can be 1 and the highest can be 2^31-1. Now every time calculate mid. If mid*mid is equal to num then return true. Else if mid*mid is greater than num then high=mid-1 else low=mid+1.

bool isPerfectSquare(int num)
{
    long long low = 1, high = (1 << 31 - 1);
    while (low <= high)
    {
        long long mid = low + (high - low) / 2;
        long long ans = mid * mid;
        if (ans == num) return true;
        else if (ans > num) high = mid - 1;
        else low = mid + 1;
    }
    return false;
}