スナップ69.xの平方根C++二分解法

int sqrt(int x)関数を実現します.
xの平方根を計算して返します.ここで、xは非負の整数です.
戻りタイプが整数であるため、結果として整数の部分のみが保持され、小数の部分は切り捨てられます.
例1:
入力:4出力:2例2:
例2:
入力:8出力:2説明:8の平方根は2.82842...で、戻りタイプが整数であるため、小数部は切り捨てられます.

int mySqrt(int x) {
     
	if (x == 1||x==0) return x;
	int low = 1, high = x - 1;
	int m=0;
	while (low <= high) {
     
		int mid = (low + high) / 2;
		/*
		if (mid > 46341) {//    ，       
			high = 46341;//  int      ，       46340
			continue;
		}
		*/
		long long chen = (long long)mid * (long long )mid;
		if (chen == x) {
      //mid*mid     ？ long long
			m = mid;//       
			break;
		}
		else if (chen > x) high = mid-1;
		else low = mid+1;
	}
	if (m != 0) return m;
	long long x1 = (long long)low * (long long)low, x2 = (long long)high * (long long)high;
	if (x1 < x && x2 < x) return (low > high) ? low : high;
	else return(x1 < x) ? low : high;
	//            
}

主な思想はすべての整数を遍歴することであり,整数秩序のために二分法を考え,他の方法にはポケットコンピューティングアルゴリズム,ニュートン反復などの非主流の方法が含まれている.