“This is the 10th day of my participation in the Gwen Challenge in November. Check out the details: The Last Gwen Challenge in 2021.”

Brush algorithm, is never to memorize the problem, but to practice the actual problem into a concrete data structure or algorithm model, and then use the corresponding data structure or algorithm model to solve the problem. In my opinion, with this kind of thinking, I can not only solve the interview problems, but also learn to think in daily work. How to abstract the actual scene into the corresponding algorithm model, so as to improve the quality and performance of the code

Square root

Sqrt(x)

Topic describes

Given a non-negative integer x, compute and return the arithmetic square root of x

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

Note: It is not allowed to use any built-in exponential functions and operators, such as POw (x, 0.5) or x ** 0.5

The sample

Example 1

Input: x = 4 Output: 2Copy the code

Example 2

Input: x = 8 Output: 2 Explanation: The arithmetic square root of 8 is 2.82842... Because the return type is an integer, the decimal part will be omittedCopy the code

Tip:

  • 0 <= x <= 2^31 - 1

The problem solving

Train of thought

Dichotomy is suitable for solving problems such as square root, median, and finding the target value in an ordered array

Finding the square root of a number is actually equivalent to finding a number between 0 and x, so that the square of the number is equal to x. Obviously, the numbers between 0 and x are in order, which perfectly fits the conditions of binary search

The problem then becomes finding the target number between 0 and x, using the standard dichotomy. Look directly at the code

code

/ / non-recursive implementation func mySqrt (int x) int {if x = = 1 | | x = = 0} {return x if x < = 0 {} return - 1 left, right: = 0, x res := -1 for left <= right { mid := left + (right-left)/2 if mid * mid <= x { res = mid left = mid + 1 } else { right  = mid - 1 } } return res }Copy the code