> For the complete documentation index, see [llms.txt](https://kongchengzhuge.gitbook.io/leetcode/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://kongchengzhuge.gitbook.io/leetcode/69.-sqrt-x.md).

# 69. Sqrt(x)

## problem description

Implement `int sqrt(int x)`.

Compute and return the square root of *x*, where *x* is guaranteed to be a non-negative integer.

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

**Example 1:**

```
Input: 4
Output: 2
```

**Example 2:**

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

## algorithm thought

第一次做这个题的时候，我也不是很清楚如何去计算一个数开根号。之后看了discuss了解到可以用二分查找。（感觉很多题都可以用二分查找，在一个大范围中找一个数，然后可以找到排除一半数的条件，条件很难找，需要仔细体会）。我记得我前几周做了一个contest也是用二分查找，当时做出来之后很惊讶。

回归题目本身，这里我们在0-x中查找是否有满足mid\*mid=x的情况

## code

```cpp
class Solution {
public:
    int mySqrt(int x) {
        if(x<=1)
             return x;
        int left=0,right=(x==INT_MAX?INT_MAX:x+1);
        while(left<right){
            int mid=left+(right-left)/2;
            if(mid>=x/mid)
                right=mid;
            else
                left=mid+1;
        }
        return left==x/left?left:left-1;
    }
};
```

## algorithm analysis

二分查找，每次可以排除一半的数字。时间复杂度O(lgx)