Moment For Technology

The square root of leetcode-069 -x

Posted on April 6, 2023, 12:33 a.m. by Gerald Watkins
Category: java Tag: java algorithm leetcode LeetCode Personal Problem Solving Summary Binary search

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: 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.
About (Moment For Technology) is a global community with thousands techies from across the global hang out!Passionate technologists, be it gadget freaks, tech enthusiasts, coders, technopreneurs, or CIOs, you would find them all here.