Implementação da função Sqrt(x);o que é $(i^2 \leq x) \land ((i + 1)^2 > x)$ verificando?

Question

Recentemente eu estava trabalhando em um Pergunta LeetCode

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.

Aqui está uma solução que eu realmente gosto e entendo, exceto por uma linha.Ele está usando a pesquisa binária para chegar à solução:

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;
}

A questão conceitual é:por que é verdade que dado um número específico, digamos $i$, $$(i^2 \leq x) \land ((i + 1)^2 > x)$$ retorna se ou não $i$ é a representação inteira truncada da raiz quadrada de $x$?(O bloco de código acima retorna na condição idêntica, mas a desigualdade é reorganizada para evitar estouro de número inteiro)

Answer 1

Vou juntar as duas desigualdades, para facilitar a leitura: $i^2 \leq x < (i+1)^2$.

Tomar o quadrado positivo de um número positivo é uma função monótona.Por isso,$$ i^2 leq x <(i+1)^2 implica i leq | sqrt {x} | <i +1 $$

Então, a parte inteira de $|\sqrt{x}|$ é obviamente $i$.