Implement int sqrt(int x).
Compute and return the square root of x.
public class Solution { public int sqrt(int x) { int left = 0; int right = x; int mid = 0; while(left <= right) { mid = left + (right - left)/2; long temp = mid*mid; if(mid != 0 && temp/mid != mid)//take out 0 { right = mid - 1; continue; } if(temp == x) return mid; else if(temp > x) right = mid - 1; else left = mid + 1; } return right; } }
public class Solution { public int sqrt(int x) { long orig=(long) x, root=0, start=0, end=orig; while(start<=end){ root=(start+end)/2; long sq=root*root; if(sq==orig) return (int) root; else if(sq>orig){ end=root-1; } else{ start=root+1; } } return (root*root>orig && (root-1)*(root-1)<orig)?(int)root-1:(int) root; } }
learned: use binary search idea get root
public class Solution { public int sqrt(int x) { if (x == 1 || x == 0) { return x; } int left = 1; int right = x; while (left < right - 1) { int mid = left + (right - left) / 2; int quo = x / mid; if (quo == mid) { return quo; // mid is too big } else if (quo < mid) { right = mid; } else { left = mid; } } return left; } }