x的平方根 二分查找

x的平方根 二分查找

​​题目链接​​

题意

给你一个数，让你求出n的平方根，这个平方根的平方一定是n以内最接近n的数。

思路

直接用java函数库里的方法sqrt方法很快就能做。 下面考虑一下二分。 首先我们限定一下l 和 r 的范围，一定是在[0, n / 2 + 1]内的。

最后的结果一定是（ans, ans + 1）中的ans

如果是判断条件等于的话，那么结果一定是r，因为此时r 在 l的左端。

import java.util.Arrays;import java.util.Comparator;import java.util.HashSet;import java.util.LinkedList;import java.util.Queue;import java.util.Scanner;import java.util.Set;class Solution { public int mySqrt(int n) { if(n == 0 || n == 1)return n; int r = n / 2 + 1; int l = 0; int ans = 0; while(r >= l) { int mid = (r + l) >>> 1; int f = n / mid; if(mid == f) { ans = f; return mid; }else if(f > mid) l = mid + 1; else r = mid - 1; } return r; }}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。