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.