Внедрение функции SQRT (X);Что такое $ (i ^ 2 \ leq x) \ земля ((i + 1) ^ 2> x) $ Checkity?

Question

Недавно я работал над reetcode Вопрос

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.

.

Вот решение, которое мне очень нравится и понимаю, за исключением одной строки.Используется бинарный поиск, чтобы добраться до решения:

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

.

Концептуальный вопрос: почему это правда, что дает определенное число, скажем, $ i $ , $$ (I ^ 2 \ leq x) \ land ((i + 1) ^ 2> x) $$ Возвращает, стоит ли $ i $ усеченныйЦелочисленное представление квадратного корня $ x $ ?(Блок кода выше возврата в одинаковом состоянии, но неравенство переставлено, чтобы избежать переполнения целого числа)

Answer 1

Я поставим два неравенства вместе, для чтения: $ I ^ 2 \ leq x <(i + 1) ^ 2 $ .

Взятие положительного квадрата положительного числа - это монотонная функция.Следовательно, $$ i ^ 2 \ leq x <(i + 1) ^ 2 \ Подразумевает i \ leq | \ sqrt {x} |

Затем мешая часть $ | \ sqrt {x} | $ Очевидно, $ i $ .