> ## Content Index
> Fetch the complete content index at: https://blog.anthea.day/llms.txt
> Use this file to discover other available public pages before exploring further.

# LeetCode 69. Sqrt(x)
- URL: https://blog.anthea.day/leetcode-c-e5-88-b7-e9-a1-8c-e7-ad-86-e8-a8-98-7/
- Published: 2022-12-27T13:17:36.000Z
- Updated: 2026-11-07T18:26:14.000Z
- Author: Anthea / 芫荽
- Tags: #Migrated-1792241843742, #Import 2026-10-17 12:57, Coding, LeetCode 刷題筆記

> Given a non-negative integer `x`, return the square root of `x` rounded down to the nearest integer. The returned integer should be **non-negative** as well.

> You **must not use** any built-in exponent function or operator.

> For example, do not use `pow(x, 0.5)` in c++ or `x ** 0.5` in python.

Example 1:

```vbnet
Input: x = 4 
Output: 2 
Explanation: The square root of 4 is 2, so we return 2.
```

Example 2:

```vbnet
Input: x = 8 
Output: 2 
Explanation: The square root of 8 is 2.82842..., and since we round it down to the nearest integer, 2 is returned.
```

Constraints:

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

#### 效能

- Time Complexity: O(log N)
- Space Complexity: O(1)
- Runtime: 20 ms
- Memory Usage: 26.6 MB

---

### 題解

回傳平方根，如果平方根不是正整數就回傳那個小數的整數位。

以 Example 2 為例，可以理解成 `2^2 < 8 < 3^3`，所以回傳 `2`。也就是說， 只要 `<= target` 就可以回傳。

---

### 二分法：兩數相乘

```kotlin
var left = 0; 
var right = x; 
var result = 0; 
 
while(left <= right) 
{ 
    var middle = left + (right - left) / 2; 
    if (middle * middle == x) 
    { 
        // 剛好相等就直接回傳 
        return middle; 
    } 
    else if (middle * middle < x) 
    { 
        // 小於就存起來，看有沒有更接近的 
        result = middle; 
        left = ++middle; 
    } 
    else 
    { 
        // 大於就繼續跑 
        right = --middle; 
    } 
} 
 
return result;
```

有通過一部分測資，代表思路應該是對的，拿著 Code 回 IDE 跑一遍才發現應該是因為 **兩數相乘** 有可能超過 `int` 的上限，才導致結果怪怪的。

---

### 超過上限：改用除法

既然用乘的會超過，那就試試用除的吧。用除法要注意的一個細節是：除數不能是 `0`，所以會使除數 `middle` 變成 `0` 的情況要避開：

```kotlin
public class Solution { 
    public int MySqrt(int x) { 
        // 0 和 1 會使 middle  = 0 
        if (x <= 1) return x; 
         
        var left = 0; 
        var right = x; 
        var result = 0; 
         
        while(left <= right) 
        { 
            var middle = left + (right - left) / 2; 
            if (middle == x / middle) 
            { 
                return middle; 
            } 
            else if (middle < x / middle) 
            { 
                result = middle; 
                left = ++middle; 
            } 
            else 
            { 
                right = --middle; 
            } 
        } 
 
        return result; 
    } 
}
```

---

#### 參考資料

- [69\. Sqrt(x)](https://leetcode.com/problems/sqrtx/description/?ref=blog.anthea.day)
- [Solutions — A Binary Search Solution](https://leetcode.com/problems/sqrtx/solutions/25047/a-binary-search-solution/?ref=blog.anthea.day)