LeetCode-69 x的平方根

题目描述：

思路想法：

暴力求解法，从 0 - x/2+1 我们从小到大遍历每个数，看看有哪个数是满足 k*k==x 返回 k ; 或者k*k>x && (k-1)*(k-1)<x 返回k-1;

复杂读O(n); 但是要注意 k*k 可能会溢出；使用 long 代替 int ； 或者 使用变相的判断 k == x/k;

二分查找的方法：

本题是满足二分查找的条件的：顺序排列，线性增加；

 

Java 代码：

一 一枚举：

class Solution { public int mySqrt(int x) { long i=0; while(i<=x/2+1){ if(i*i>x) return (int)i-1; i++; } return 1; } }

 

二分查找：

class Solution { public int mySqrt(int x) { if (x==0){return 0;} int left = 1; int right = x/2+1; while (left<=right){ int mid = left + (right-left)/2; if (mid<x/mid+1){ left = mid+1;} else if(mid*mid==x){return mid;} else{ right=mid-1;} } return left-1; } }

核心技能：

二分查找写的溜不溜，整数溢出会出现不可思议的结果。