问题：给定一个正整数，如果它有正整数平方根，则求出它的平方根；如果它没有正整数平方根，则求出最接近的正整数平方根。不能使用sqrt(_: )函数。
比如说，5、6、7、8都是没有正整数平方根的，但是最接近它的正整数平方根是2，而9的正整数平方根是3。现在要求写一个函数，能够计算出给定正整数的正整数平方根，或者最接近它的正整数平方根。
这个问题的解决方案有好几种，我们先来给一个性能比较差，并且有bug的解决方案：
// 性能不好，并且有bug
func challenge(input: Int) -> Int {
for i in 0 ... input / 2 {
if i * i > input {
return i - 1
}
}
return 0
}
challenge(input: 15) // 答案3
上面这段代码比较智障，因为它只能计算[6, +∞)之间的数据，而在计算[1, 5]之间的数据时，会有问题。并且，需要计算的数据越大，程序的性能就越差。所以，这个肯定不是最终的解决方案。
一个比较好的解决方案是使用二分查找法(Binary Search)，既能完美解决bug，又极大的提高了计算性能。二分查找的思想是：先确定一个最低点x(往往从0开始)，再确定一个最高点y(一般从N / 2 + 1开始)，当x < y时，找到x和y的中间值z，然后用中间值z去和结果做对比，如果刚好就是z，则直接返回中间值z；如果结果还是比z大，说明我们找到的值z小了，还需要继续往更大的值上去查找，此时应该将中间值z赋值给最低点x，然后继续寻找x和y的中间值；如果结果比z小，说明我们找到的值z太大了，需要继续往更小的值上去查找，此时应该将中间值z赋值给最高点y，然后继续寻找x和y的中间值...一次类推，直至找到合适的中间值z，然后再将其返回。用代码表示为：
func challenge1(input: Int) -> Int {
// 如果输入的数据恰好是1，则直接返回结果1
guard input != 1 else { return 1 }
// 指定最高点和最低点
var lowerBound = 0
var upperBound = 1 + input / 2
// 当最低点加1小于最高点时，进入循环体
while lowerBound + 1 < upperBound {
// 确定中间点
let middle = lowerBound + ((upperBound - lowerBound) / 2)
// 对中间点进行平方操作
let middleSquared = middle * middle
// 对middleSquared和输入数据进行对比
if middleSquared == input {
// 如果middleSquared恰好和input相等，则说明middle符合题目要求，直接将其返回
return middle
} else if middleSquared < input {
// 如果middleSquared比input还小，则说明middle太小了
// 还要继续往更大的值上去查找，将middle设置为最低点，并继续下一次循环
lowerBound = middle
} else {
// 如果middleSquared比input还大，则说明middle太大了
// 还需要继续往更小的值上去查找，将middle设置为最高点，并继续下一次循环
upperBound = middle
}
}
// 返回lowerBound的值
return lowerBound
}
challenge1(input: 5) // 结果为2
还有一个抖机灵的做法，题目说了不能使用sqrt(_: )函数，但是没有说不能使用pow(_: , _: )函数呀，所以我们可以利用幂函数来达到开方的目的：
// 性能又好又简洁
func challenge3(input: Int) -> Int {
// 使用幂函数来实现开方的目的
return Int(floor(pow(Double(input), 0.5)))
}
有时候合理的利用系统自带的函数，可以极大的减少我们的开发工作。顺便提一下几个常用的数学函数：
func sqrt(_: Double) -> Double 平方根函数
func pow(_: Double, _: Double) -> Double 幂函数
func floor(_: Double) -> Double 向下取整函数
func ceil(_: Double) -> Double 向上取整函数
网友评论