DOJO004

Dashool 創辦人
喜歡調酒
Rails、Nextjs、TypeScript

來刷 LeetCode 吧! 20 69.Sqrt(x)

LeetCode

https://leetcode.com/problems/sqrtx/description/

題目

給一個非負整數 x，回傳 x 的開根號。

向下取最接近的整數。

不要使用內建的運算符號、指數函式。

解答 - 使用 Math.sqrt()

簡單明瞭，一看就知道在做什麼事情。

var mySqrt = function (x) {
  return Math.floor(Math.sqrt(x));
};

解答 - 使用二分法

效能大幅提升

var mySqrt = function (x) {
  if (x < 2) return x;
  
  let left = 1, right = x, result = 0;
  
  while (left <= right) {
    let mid = Math.floor((left + right) / 2);
    if (mid * mid === x) {
      return mid;
    } else if (mid * mid < x) {
      left = mid + 1;
      result = mid;
    } else {
      right = mid - 1;
    }
  }
  
  return result;
};

x < 2 直接回傳 x，最小的平方根就是 1 。
初始化 left = 1，right = x。result 用來儲存最後 mid 的值。
開始迴圈：
1. 先找出 mid 的位置
2. mid * mid = x，代表正好為 x 的開根號，直接回傳
3. mid * mid < x ，將 left = mid + 1，將 mid 儲存至 result
4. mid * mid > x，將 right = mid - 1
5. 最後當迴圈結束時回傳 result