Sqrt(x)

描述

Implement int sqrt(int x).

Compute and return the square root of x.

分析

二分查找

代码

  1. // LeetCode, Sqrt(x)
  2. // 二分查找
  3. // 时间复杂度O(logn)，空间复杂度O(1)
  4. class Solution {
  5. public:
  6.     int mySqrt(int x) {
  7.         int left = 1, right = x / 2;
  8.         int last_mid;  // 记录最近一次mid
  10.         if (x < 2) return x;
  12.         while(left <= right) {
  13.             const int mid = left + (right - left) / 2;
  14.             if(x / mid > mid) { // 不要用 x > mid * mid，会溢出
  15.                 left = mid + 1;
  16.                 last_mid = mid;
  17.             } else if(x / mid < mid) {
  18.                 right = mid - 1;
  19.             } else {
  20.                 return mid;
  21.             }
  22.         }
  23.         return last_mid;
  24.     }
  25. };

相关题目

原文: https://soulmachine.gitbooks.io/algorithm-essentials/content/cpp/divide-and-conquer/sqrt.html