Mise en œuvre de la fonction SQRT (x);Qu'est-ce que $ (i ^ 2 \ \ leq x) \ terres ((i + 1) ^ 2> x) $ vérifier?
-
29-09-2020 - |
Question
Récemment, je travaillais sur un Question 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.
Voici une solution que j'aime vraiment et que je comprends, sauf une ligne.Il utilise une recherche binaire pour accéder à la 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;
}
La question conceptuelle est la suivante: pourquoi est-il vrai qu'Enon donné un numéro particulier, disons $ i $ , $$ (i ^ 2 \ leq x) \ terre ((i + 1) ^ 2> x) $$ retourne si $ i $ est le tronquéReprésentation entière de la racine carrée de $ x $ ?(Le bloc de code ci-dessus renvoie sur la condition identique, mais l'inégalité est réarrangée pour éviter le débordement entier)
La solution
Je vais mettre les deux inégalités ensemble, pour la lisibilité: $ i ^ 2 \ leq x <(i + 1) ^ 2 $ .
.Prendre le carré positif d'un nombre positif est une fonction monotone.D'où, $$ i ^ 2 \ leq x <(i + 1) ^ 2 \ implique i \ Leq | \ sqrt {x} |
Puis, la partie intergersion de $ | \ sqrt {x} | $ est évidemment $ i $ .