تنفيذ وظيفة SQRT (X)؛ما هو $ (i ^ 2 \ leq x) \ Land ((i + 1) ^ 2> x) $ التحقق؟

Question

مؤخرا كنت أعمل على leetcode سؤال

giveacodicetagpre.

هنا هو الحل الذي أعجبني حقا وفهمه، باستثناء سطر واحد.يستخدم البحث الثنائي للوصول إلى الحل:

giveacodicetagpre.

السؤال المفاهيمي هو: لماذا صحيح أن إعطاء رقم معين، يقول $ 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 $ .