[LeetCode]69. Sqrt(x)

题目描述

思路

由于题目要求返回的是整数，简单实现的话可以使用二分 注意实现过程中的一些越界问题

代码

#include <iostream> using namespace std; class Solution { public: int mySqrt(int x) { if (x == 1) return 1; int start = 0, end = x; while (start < end) { //越界点1 end + start 会越界 int mid = ((end - start) >> 1) + start; //越界点2 mid * mid 会越界 if (mid == x / mid) return mid; else if (start == mid || end == mid) return start; else if (mid < x / mid) start = mid; else end = mid; } return end; } }; int main() { Solution s; cout << s.mySqrt(2147395599) << endl; system("pause"); return 0; }