C# LeetCode 69: Sqrt(x)
Problem
Given a non-negative integer x, return the square root of x rounded down to the nearest integer. The returned integer should be non-negative as well.
You must not use any built-in exponent function or operator.
For example, do not use pow(x, 0.5) in c++ or x ** 0.5 in python.
Example 1:
Input: x = 4
Output: 2
Explanation: The square root of 4 is 2, so we return 2.
Code
public int MySqrt(int x)
{
if (x < 2) return x;
int left = 1, right = x / 2;
int answer = 0;
while (left <= right)
{
int mid = left + (right - left) / 2;
long square = (long)mid * mid;
if (square == x)
{
return mid;
}
else if (square < x)
{
answer = mid;
left = mid + 1;
}
else
{
right = mid - 1;
}
}
return answer;
}
Approach – Binary Search
The solution uses binary search to efficiently find the integer square root.
Edge Case:
If x < 2, return x directly (0→0, 1→1).
Search Range:
- The square root of x is at most x / 2 for x >= 2. So we search between 1 and x / 2.
Binary Search Mechanics:
-
Pick the middle number
mid. -
Compute mid * mid (cast to long to avoid overflow).
-
If mid * mid == x → return mid (perfect square).
-
If mid * mid < x → move left up to mid + 1 and record mid as answer.
-
If mid * mid > x → move right down to mid – 1.
Return the last recorded answer because it’s the floor of the square root.
By using the Binary Search mechanics, we reduce the numbers needing to be checked can be halved each time, halving the amount of effort needed to find the correct number.
As always drop me a follow on DevTo or twitter/x to hear about future articles like this.
