Recently I was working on a LeetCode question
Compute and return the square root of x, where x is guaranteed to be a non-negative integer.
Since the return type is an integer, the decimal digits are truncated and only
the integer part of the result is returned.
Example 1:
Input: 4
Output: 2
Example 2:
Input: 8
Output: 2
Explanation: The square root of 8 is 2.82842..., and since
the decimal part is truncated, 2 is returned.
Here is a solution that I really like and understand, except for one line. It is using binary search to get to the solution:
int mySqrt(int x) {
if (x == 0) return x;
int left = 1, right = INT_MAX, mid;
while(left < right) {
mid = left + (right - left)/2;
if (mid <= x / mid && (mid + 1) > x / (mid + 1)) {
return mid;
}
if (mid < x/mid) {
left = mid + 1;
} else { // mid > x/mid
right = mid;
}
}
return right;
}
The conceptual question is: why is it true that given a particular number, say $i$, $$(i^2 \leq x) \land ((i + 1)^2 > x)$$ returns whether or not $i$ is the truncated integer representation of the square root of $x$? (The code block above returns on the identical condition, but inequality is rearranged to avoid integer overflow)