1回答

liuyubobobo

2019-04-04

已采纳

最简单的方法，是使用二分搜索法，搜索出一个浮点数，也就是sqrt(x)的解，然后取整数部分就好了。

我的这个思路的解法，可以参考：

https://github.com/liuyubobobo/Play-Leetcode/blob/master/0069-Sqrt-x/cpp-0069/main2.cpp

如果完全在整数范围解决这个问题，也是可以的。相当于，用二分搜索法，找到一个a，使得a*a是小于x的最大值。这是一个经典的，用二分查找法的思路，求解ceil的问题：搜索到小于（或者等于）x的最大值。和ceil问题相对应的，还有floor问题。搜索到大于（或等于）x的最小值。

在我的《数据结构于算法》课程的补充代码中，给出了二分搜索法求解这两个问题的代码：

https://github.com/liuyubobobo/Play-with-Algorithms/blob/master/05-Binary-Search-Tree/Course%20Code%20(C%2B%2B)/Optional-02-Floor-and-Ceil-in-Binary-Search/main.cpp

对于这个问题，这个思路的解法，可以参考我的代码：

https://github.com/liuyubobobo/Play-Leetcode/blob/master/0069-Sqrt-x/cpp-0069/main.cpp

继续加油！：）

1

1

软件工程小白菜

多谢老师指点！

2019-04-05

共1条回复