LeetCode 69

概述

​ 模拟sqrt函数实现

思路

• 对于一个整数的平方根，除了几个特殊情况，可以验证<=x/2。这里强调是整数，所以2,3仍然符合，而0,1则要特殊处理。

• 使用二分法，while循环中的if条件要注意，如果mid*mid>x,那么结果在mid之后；反正则不一定

  int mySqrt(int x) {
  	if(x==0)	return 0;
      if(x==1)	return 1;
      int start=1;
      int end=x/2;
      int ans=-1;
      while(end>=start){	
          int mid=start+(end-start)/2;
          if((long long)mid*mid>x)	//比x大，那么一定在前面
              end=mid-1;
          else{	//<=x，不一定先记录下来
              ans=mid;	//可能的结果先保存下来，所以end可以等于start
              start=mid+1;	//继续二分
          }
      }
      return ans;

• 如果不用x/2,那么就不需要特殊情况单独处理

  int mySqrt(int x) {
      int start=0;
      int end=x;	//v
      int ans=-1;
      while(end>=start){
          int mid=start+(end-start)/2;
          if((long long)mid*mid>x)
              end=mid-1;
          else{
              ans=mid;
              start=mid+1;
          }
      }
      return ans;
   }