SQRT (X) Attuazione della funzione;Cos'è $ (I ^ 2 \ Leq X) \ Land ((I + 1) ^ 2> x) $ Verifica?
-
29-09-2020 - |
Domanda
Recentemente stavo lavorando su un Domanda 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.
.
Ecco una soluzione che mi piace e capire molto, ad eccezione di una riga.Sta usando la ricerca binaria per arrivare alla soluzione:
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 domanda concettuale è: perché è vero che ha dato un numero particolare, dì $ I $ , $$ (I ^ 2 \ Leq X) \ Land ((I + 1) ^ 2> x) $$ restituisce se $ i $ è il troncatoRappresentazione intera della radice quadrata di $ x $ ?(Il blocco del codice sopra ritorna sulla condizione identica, ma la disuguaglianza viene riorganizzata per evitare un overflow integro)
Soluzione
Metterò insieme le due disuguaglianze, per la leggibilità: $ i ^ 2 \ leq x <(I + 1) ^ 2 $ .
Prendendo il quadrato positivo di un numero positivo è una funzione monotono.Quindi, $$ I ^ 2 \ Leq x <(I + 1) ^ 2 \ implica I \ Leq | \ sqrt {x} |
Quindi, la parte interurlica della $ | \ sqrt {x} | $ è ovviamente $ I $ .