69.sqrt_x.md

69. Sqrt(x)

简单

https://leetcode-cn.com/problems/sqrtx/

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

Since the return type is an integer, the decimal digits are truncated, and only the integer part of the result is returned.

Note: You are not allowed to use any built-in exponent function or operator, such as pow(x, 0.5) or x ** 0.5.

Example 1:

Input: x = 4
Output: 2

Example 2:

Input: x = 8
Output: 2
Explanation: The square root of 8 is 2.82842..., and since the decimal part is truncated, 2 is returned.
 

Constraints:

0 <= x <= 231 - 1

相关标签

• Math
• Binary Search

相似题目

• Pow(x, n) 中等
• Valid Perfect Square 简单

隐藏提示1

• Try exploring all integers. (Credits: @annujoshi)

隐藏提示2

• Use the sorted property of integers to reduced the search space. (Credits: @annujoshi)

sol

直接对答案可能存在的区间进行二分 => 二分答案

class Solution:
    def mySqrt(self, x: int) -> int:
        if x == 0:
            return 0
            
        start, end = 0, x
        while start + 1 < end:
            mid = start + (end - start) // 2
            midsquare = mid * mid # cannot mid^2
            if midsquare == x:
                return mid
            elif midsquare > x:
                end = mid
            else:
                start = mid
        
        if end * end <= x: # must first
            return end
        if start * start <= x:
            return start
        return -1