Use binary search to solve this problem. Start with left as 1 and right as x. Then find the mid point and test by squaring it. If mid * mid is equal to x then we have our answer. If the mid*mid is smaller than x then we need to lower our search, so we reduce our search range by looking between left and mid. If the square was bigger than x then we search between mid and right. We repeat this until we find an exact match or our left and right pointers overlap. If they overlap then mid is slightly too big and we need to return mid-1. There are a few edge cases to consider:
Just be careful about integer overflow. One of the test cases has x as close to INT_MAX, which would cause integer overflow in our initial mid*mid calculation. I overcome this by checking against a limit for mid (46340, which is the square root of INT_MAX) so that the square cannot exceed the integer limit. I noticed on leetcode that most solutions use a long variable to calculate the square, which on Unix systems (LP64) will work but not on Windows (LLP64).
