给定整数n,求离根号n最近的整数。
如题，如何使用二分查找实现#笔试题目#
2019-08-13 10:21 已编辑 西安交通大学 算法工程师
关注
全部评论
旦旦小算法
复旦大学 算法工程师
def func(n):
p = 0.618
i = 0
j = n
while i<=j:
mid = int(p*i + (1-p)*j)
if abs(mid*mid-n)<=abs((mid-1)*(mid-1)-n) and abs(mid*mid-n)<=abs((mid+1)*(mid+1)-n):
return mid
elif abs((mid-1)*(mid-1)-n)<=abs(mid*mid-n) and abs(mid*mid-n)<=abs((mid+1)*(mid+1)-n):
j = mid - 1
else:
i = mid + 1
望秦
山东大学 Java
private static int core(int n){
int small=0,big=n/2+1,mid=0;
while(small<big){
mid = small+(big-small)/2;
if(mid*mid>n) big = mid-1;
else if(mid*mid<n) small=mid+1;
else return mid;
}
int s=0,e=0;
if(mid*mid>n){
s = mid-1;e = mid;
}else{
s = mid;e = mid+1;
}
double m = (s+e)/2.0;
if(m*m<n) return e;
else return s;
}
Funny.
清华大学 算法工程师
import numpy as np
def bin_search_sqrt(num):
left, right = 0, num
while right - left > 1:
mid = (left + right) // 2
if mid ** 2 > num:
right = mid
else:
left = mid
return right if right**2 - num < num - left**2 else left
for i in range(15, 37):
print(i,bin_search_sqrt(i),np.sqrt(i))输出： 16 4 4.0
17 4 4.12310562562
18 4 4.24264068712
19 4 4.35889894354
20 4 4.472135955
21 5 4.58257569496
22 5 4.69041575982
23 5 4.79583152331
24 5 4.89897948557
25 5 5.0
26 5 5.09901951359
27 5 5.19615242271
28 5 5.29150262213
29 5 5.38516480713
30 5 5.47722557505
31 6 5.56776436283
32 6 5.65685424949
33 6 5.74456264654
34 6 5.83095189485
35 6 5.9160797831
36 6 6.0看上去好像是可以的？
baoluozongjuesai
门头沟学院 数据分析师
def find_nearest_n(number):
left = 0
right = number
while right-left >= 0.01:
if ((left+right)/2)**2 == number:
return (left+right)/2
elif ((left+right)/2)**2 > number:
right = (left+right)/2
else:
left = (left+right)/2
if int(right) > int(left):
return int(right)
elif left - int(left) < 0.5:
return int(left)
else:
return int(left)+1 阈值可以再调大一点 应该有还有更好的方法
老白金
门头沟学院 C++
牛顿割线法
托马斯201903231904798
西安交通大学 Java
Sqrt(n)四舍五入不行吗？
ChessC
浙江大学 Java
一次找小于sqrt(n)中最大的，一次找大于之中最小的，再比较这样？
相关推荐
查看8道真题和解析 点赞 评论 收藏
分享
10-23 10:26
山东大学 前端工程师 
点赞 评论 收藏
分享
11-09 09:27
兰州大学 大数据开发工程师 点赞 评论 收藏
分享