The square root of x

Int SQRT (int x)

Calculates and returns the square root of x, where x is a non-negative integer.

Since the return type is an integer, only the integer part of the result is retained, and the fractional part is omitted.

Examples can be found on the LeetCode website.

Source: LeetCode link: leetcode-cn.com/problems/sq… Copyright belongs to the Collar buckle network. Commercial reprint please contact official authorization, non-commercial reprint please indicate the source.

Solution one: dichotomy

Set min to 1, Max to 46340, and mid to the approximate value of math.sqrt (integer.max_value) :

  • ifmid*midIs equal to x, it returns directlymid;
  • ifmid*midLess than x, min is set to mid+1, and the next round of judgment is conducted again.
  • ifmid*midIf the value is greater than x, Max is set to mid-1 and the next round of judgment is conducted again.
  • The termination condition is Max not greater than min.

Finally, return 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)); }}Copy the code

Your efforts today are the foreshadowing of luck. Your efforts today are the flowers of tomorrow.