The square root of leetcode-069 -x

Square root of x

Implement int SQRT (int x).

Calculates and returns the square root of x, where x is a nonnegative integer.

Since the return type is an integer, the result preserves only the integer portion; the fractional portion is discarded.

See the LeetCode website for an example.

Source: LeetCode Link: https://leetcode-cn.com/probl... Copyright belongs to collar network. Commercial reprint please contact the official authorization, non-commercial reprint please indicate the source.

Solution one: dichotomy

First set a minimum value of min to 1, and a maximum value of Max to 46340 is approximately equivalent to Math.sqrt(Integer.max_value), then mid is the middle value:

• ifmid*midEquals x, it just returnsmid;
• ifmid*mid x, then set min as Mid +1 to make the next round of judgment again;
• ifmid*midIf the value is greater than x, the Max is set to mid-1, and the next judgment is made again.
• The termination condition is that Max is not greater than min.

And then we go back to Mid.

public class LeetCode_069 { public static int mySqrt(int x) { int min = 1, max = 46340, mid = 1; mid = (min + max) / 2; while (min  max) { int temp = mid * mid; if (temp == x) { return mid; } else if (temp  x) { min = mid + 1; } else { max = mid - 1; } mid = (min + max) / 2; } return mid; } public static void main(String[] args) { System.out.println(mySqrt(4)); }}

【 Daily Message 】 Your efforts today, is lucky foreshadowing, the present pay, is tomorrow's flowers.