java牛客简单题

NC32 求平方根
描述&＃xff1a;
实现函数 int sqrt(int x).
计算并返回 x 的平方根&＃xff08;向下取整&＃xff09;

数据范围&＃xff1a; 0 <&＃61; x <2^{31}-10<&＃61;x<2
31
−1
要求&＃xff1a;空间复杂度 O(1)O(1)&＃xff0c;时间复杂度 O(logx)O(logx)

题解如下&＃xff1a;

import java.util.*;
public class Solution {/*** * &＃64;param x int整型 * &＃64;return int整型*/public int sqrt (int x) {// write code hereif(x&＃61;&＃61;0) return 0;int left&＃61;1;int right&＃61;x/2;while(left<right){int mid&＃61;(left&＃43;right)/2&＃43;1;if(mid>x/mid)right&＃61;mid-1;elseleft&＃61;mid;}return left;}
}


这个题虽然简单&＃xff0c;但是也有一些二分法的解题亮点&＃xff0c;便记录一下。
记得刚学c语言的时候在一本书中看到过这个题&＃xff0c;不过他给的题解是利用数学知识给的一个取值范围&＃xff0c;具体是啥忘记了。以后遇到再看看吧。