SQRT(X)関数実装。$(i ^ 2 \ leq x)\ land((i + 1)^ 2> x)$チェックとは何ですか?
-
29-09-2020 - |
質問
最近私は letercode質問
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 $ の平方根の整数表現?(上記のコードブロックは同じ条件で戻りますが、整数のオーバーフローを回避するために不等式が並べ替えられます)
解決
読みやすさのために、2つの不等式を一緒にします。 $ i ^ 2 \ leq x <(i + 1)^ 2 $ 。
正数の正方形を取ることはモノトーン機能です。したがって、 $$ i ^ 2 \ leq x <(i + 1)^ 2 \ Inglies i \ Leq | \ sqrt {x} |
その後、 $ | \ sqrt {x} | $ は明らかに $ i $ 。
所属していません cs.stackexchange