---
tags: LeetCode
---

# 69. Sqrt(x)

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.

輸入範本如下

public class Solution {
    public int MySqrt(int x) {
        
    }
}

### 直覺想法
用二分搜尋法去逼近答案.

40 ms	14.8 MB
You are here!
Your runtime beats 83.43 % of csharp submissions.
// 使用二分搜尋
public int MySqrt(int x)
{
    int low = 0, high = x / 2 + 1; // + 1 是為了處理 x = 1 使 high = 0 的 case
    while (low <= high)
    {
        // high + low 的結果可能會導致 Overflow , 使用 long 又必須轉型. 花時間
        int mid = low + (high - low) / 2; 
        long powValue = (long)mid * mid; // 閃不過 , 必須使用 long
        if (powValue == x)
        {
            return mid;
        }
        else if (powValue < x)
        {
            low = mid + 1;
        }
        else
        {
            high = mid - 1;
        }
    }
    // 離開 While (low<=high) 的時候 low 一定大於正確答案且 high 一定小於正確答案. 此題會希望若無解 , 回傳最接近小於正確答案的值 
    return high;
}

// 132 ms	14.7 MB
// 暴力法 , 直接從 0 開始 一個一個 try
public int MySqrt(int x)
{
    int low = 0, high = x / 2 + 1, ans = 0;
    for (; low <= high; low++)
    {
        long powValue = (long)low * low;
        if (powValue == x)
        {
            return low;
        }
        else if (powValue < x)
        {
            ans = low;
        }
        else
        {
            break;
        }
    }
    return ans;
}


36 ms	14.8 MB
You are here!
Your runtime beats 97.11 % of csharp submissions.
// 牛頓法
public int MySqrt(int a)
{
    // 牛頓法公式 , 可以透過 Xn 得到 Xn+1
    // 所以只要目前 Xn 的結果 約等於 Xn * Xn = x + 誤差 , 該 Xn 就是答案了

    const double epsilon = 1e-6; // 誤差精度
    double xn = a;
    while (xn * xn > a + epsilon)
    {
        xn = (xn + a / xn) / 2;
    }
    return (int)xn;
}

### 參考資源
[Searching Sorted List](https://www.cs.usfca.edu/~galles/visualization/Search.html)
[淺談二分搜尋法](https://blog.techbridge.cc/2016/09/24/binary-search-introduction/)
- 1. 保證答案一定在閉區間 [L, R] 裡面
2. 當這區間剩下的數很少時，改用線性搜尋

[How to Implement Integer Square Root in C/C++?](https://helloacm.com/coding-exercise-implement-integer-square-root-c-online-judge/)
- 圖的公式是錯的.

[怎麼用牛頓法解平方根？](https://www.itread01.com/content/1544934182.html)

[淺談二分搜尋法](https://blog.techbridge.cc/2016/09/24/binary-search-introduction/)

### Thank you!

You can find me on

- [GitHub](https://github.com/s0920832252)
- [Facebook](https://www.facebook.com/fourtune.chen)

若有謬誤 , 煩請告知 , 新手發帖請多包涵

# :100: :muscle: :tada: :sheep: