Cacher is the code snippet organizer for pro developers

//pow(x,k)
//二分搜索
public double mypow(int x,int n){
  if(n==0) return 1;
  if(n==1) return x;
  double half = mypow(x,n/2);
  if(n%2==0) return half*half;
  if(n>0) return half*half*x;
  return half*half/x;
}

//求一个数的平方根，输入数字x是一个Integer,输出结果是一个Integer
//二分查找法
public int mine_sqrt(int x){
  int left = 1,right=x-1;
  if(x==1) return 1;
  while(left < right){
    int mid = left+(right-left)/2;
    if(x/mid==mid) return mid;
    else if(x/mid > mid) left = mid+1;
    else right=mid;//这里right不等于mid+1,而left等于mid+1
  }
  return right-1;
}

//给定一个正数求其平方根
//另一种二分查找法
public int my_sqrt(int x){
  int left=  1;
  int right = x/2+1;
  while(left <= right){
    int mid = left+(right-left)/2;
    if(mid*mid==x) return mid;
    else if(x/mid>mid) left = mid+1;
    else right=mid-1;
  }
  return right;
}

//求解一个正整数的平方根，返回正整数
//牛顿迭代法：https://www.cnblogs.com/AnnieKim/archive/2013/04/18/3028607.html
public int newtun_sqrt(int x){
  double res = x-1;
  while(res*res-x>0.0001){
    res = (res+x/res)/2;
  }
  return int(res);
}