import java.util.*; public class Solution { /** * * @param x int整型 * @return int整型 */ public int mysqrt (int x) { if(x < 1) return 0 ; if(x < 4) return 1 ; int half = x / 2 ;//当x >= 4 时 x^(1/2) 一定 <= x/2 , 因此直接定位到[0-x/2] int i = 0 ; int j = half ; while(i <= j) {//二分查找 int mid = i + (j - i) / 2 ; if(mid == x / mid) {//将条件【mid * mid == x】 转换为 【mid == x/mid】,避免溢出 return mid ; } else if(mid < x / mid) { if((mid + 1) > x / (mid + 1)) { return mid ; } i = mid + 1; } else { j = mid - 1 ; } } return j ; } }