Integer Square Root

This challenge asks you to implement a function that calculates the integer square root of a non-negative integer. This is a fundamental operation with applications in various algorithms, including optimization, geometry, and numerical analysis. You will need to find the largest integer whose square is less than or equal to the input number.

Problem Description

You are tasked with writing a function integerSqrt(x) that takes a non-negative integer x as input and returns its integer square root. The integer square root of x is defined as the largest integer y such that y * y <= x. You are not allowed to use any built-in exponentiation functions or operators (like pow(x, 0.5) or x ** 0.5).

Key Requirements:

• The function must accept a single non-negative integer argument.
• The function must return a non-negative integer.
• The returned integer must be the largest integer whose square is less than or equal to the input x.
• Built-in functions for calculating square roots or powers are forbidden.

Expected Behavior:

• For a given input x, the function should return y such that y * y <= x and (y + 1) * (y + 1) > x.

Edge Cases to Consider:

• Input x = 0.
• Input x = 1.
• Large input values where y * y might overflow standard integer types (though for this challenge, assume standard integer types are sufficient unless specified otherwise by constraints).

Examples

Example 1:

Input: 4
Output: 2
Explanation: 2 * 2 = 4. (2+1) * (2+1) = 9, which is greater than 4. So, 2 is the integer square root.

Example 2:

Input: 8
Output: 2
Explanation: 2 * 2 = 4. 3 * 3 = 9, which is greater than 8. So, 2 is the integer square root.

Example 3:

Input: 0
Output: 0
Explanation: 0 * 0 = 0. (0+1) * (0+1) = 1, which is greater than 0. So, 0 is the integer square root.

Example 4:

Input: 1
Output: 1
Explanation: 1 * 1 = 1. (1+1) * (1+1) = 4, which is greater than 1. So, 1 is the integer square root.

Constraints

• 0 <= x <= 2^31 - 1 (inclusive).
• The input x will always be a non-negative integer.
• Your solution should aim for an efficient time complexity. A naive linear search might be too slow for the upper bound of x.

Notes

• Think about the properties of square roots. The integer square root y will always be less than or equal to x (for x >= 1).
• Consider algorithms that can efficiently search for a value within a range. Binary search is a strong candidate here.
• Be mindful of potential integer overflow if you are using languages with fixed-size integer types, though the given constraint should be manageable with standard integer types in most languages.