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

# 69. Sqrt(x)

## 1.問題

* 實作sqrt

![](https://901207480-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LGKoChvN9am4__HCIRK%2F-LNbfaAKz0WhJWb-rltV%2F-LNc8t1nNPfBQt0djSh9%2F%E8%9E%A2%E5%B9%95%E5%BF%AB%E7%85%A7%202018-09-30%20%E4%B8%8A%E5%8D%889.45.56.png?alt=media\&token=032bb24f-c760-4049-81d5-45743c2fdd81)

## 2.想法

* 提問
* function header, parameter
* test input
* 說明想法 
  * edge case: x == 0
  * binary search
    * 初始狀態為left = 1, right = x
    * 當x / mid == mid, 回傳mid
    * 當x / mid > mid 時
      * 表示目標在mid右邊, 因此讓left = mid
      * 或是目標介於mid \* mid與x間, 回傳mid
    * 當x / mid < mid時
      * 表示目標在mid左邊, 因此讓right = mid
      * 或是目標介於x 與 mid \* mid間, 回傳x
* 測試計算複雜度

## 3.程式碼

```
class Solution {
public:
    int mySqrt(int x) {
        return binarySearch(1, x, x);
    }
private:
    int binarySearch(long left, long right, long target) {
        if (left > right) {
            return 0;
        }
        
        long mid = (left + right) / 2;
        long x = target / mid;
        
        if (mid == x) {
            return mid;
        }
        
        if (x > mid) {
            if (x - mid == 1) {
                return mid;
            }
            return binarySearch(mid + 1, right, target);
        } else {
            if (mid - x == 1) {
                return x;
            }
            return binarySearch(left, mid - 1, target);
        }
    }
};
```