Learner Level
Implement the integerSquareRootFloor method that returns the floor value of the square root of an integer.
The input contains a non-negative integer n. Your task is to return the floor value of its square root.
The floor square root is the largest integer x such that x * x is less than or equal to n. For example, the square root of 17 is a little more than 4, so the answer is 4.
Example 1
Input
n (int) =
17Returns (int)
4Example 2
Input
n (int) =
4Returns (int)
2Example 3
Input
n (int) =
8Returns (int)
2Use binary search between 0 and n to find the largest number whose square is not greater than n.
For each middle value, compare middle * middle with n. If the square is valid, store it as a possible answer and search to the right for a bigger valid value.
If the square is too large, search to the left.
Pseudocode:
function integerSquareRootFloor(n):
left = 0
right = n
answer = 0
while left <= right:
mid = left + (right - left) / 2
square = mid * mid
if square <= n:
answer = mid
left = mid + 1
else:
right = mid - 1
return answerReady to test your solutionRun Code checks your solution against the test cases.Shift + Enter to run