# LeetCode Easy 69. Sqrt(x)

tags: leetcode

問題

• Explore
• Problems

int sqrt(int x)を実装せよ

xの平方根を計算し返せ. xは非負整数だと保証されている

返り値は整数であるから, 小数は切り捨てられ結果の整数部分だけが返される

アイデア

全探索

全ての数を$0$から試すと答えは出ます

しかし, 時間計算量が$O(\sqrt{N})$となり非効率的です. ここでは$x$が大きくなるほどその平方根も大きくなるという単調性に注目します

ちなみに

ちなみに全探索はこんな風に書けます

class Solution {
public:
  int mySqrt(int x) {
    long i = 0; // for overflow
    while (true) {
      if (i * i == x) {
        break;
      } else if (i * i > x) {
        i--;
        break;
      }
      ++i;
    }
    return i;
  }
};

解法

• 答えとなりうる範囲は$[0, \sqrt{x}]$です
• このとき, xが0のときは0, 0より大きく4より小さい時は1を返し, それ以外では$[0, x/2]$の範囲に答えがあるということを利用すると高速に探索することが出来るのでこれを使います
• 二分探索でいつもやるようにmid = left + (right - left) / 2として, midの2乗がxより大きいかどうかで分岐させます
  • 大きくない時は範囲の右側に答えがあるので, left = mid + 1とし, 答えを更新します
    • ここで答えを更新することで整数部を切り下げする場合に対応が出来ます
  • 大きい時は範囲の左側に答えがあるので, right = mid - 1とします.
  • オーバーフローを起こさないようにxをmicで割り, この値とmidを比較します
• これがleft > rightとなるまで続けます

計算量

二分探索で, 再帰的に実行をしていないので

• 時間計算量
  • $O(\log x)$
• 空間計算量
  • $O(1)$

C++

class Solution {
public:
  int mySqrt(int x) {
    if (x == 0) return 0;
    if (0 < x && x < 4) return 1;
    
    int left = 1, right = x/2, res = 0;
    while (left <= right) {
      int mid = left + (right - left) / 2;
      if (mid <= x / mid) {
        left = mid + 1;
        res = mid;
      } else {
        right = mid - 1;
      }
    }
    return res;
  }
};