【Leetcode】Sqrt(x)

Implement int sqrt(int x).

Compute and return the square root of x.

 1 class Solution {
 2 public:
 3     int sqrt(int x) {
 4         if (x < 2) return x;
 5         int start = 1, end = x / 2;
 6         int last_mid; // 记录最近一次mid, 无整数解时输出近似解，下取整
 7         while(start <= end) {
 8             int mid = (start + end) / 2;
 9             if(x / mid > mid) { // 不要用x > mid * mid，会溢出
10                 start = mid + 1;
11                 last_mid = mid;
12             } else if(x / mid < mid) {
13                 end = mid - 1;
14             } else {
15                 return mid;
16             }
17         }
18         return last_mid;
19     }
20 };

View Code

二分查找。Morgen Stanley的电面就问了这个.