【LeetCode】69. Sqrt(x)

问题描述

https://leetcode.com/problems/sqrtx/#/description

Implement int sqrt(int x).

Compute and return the square root of x.

算法

使用折半查找即可，但要注意整型溢出

代码

public int mySqrt(int x) {
	int left = 1, right = x;	    	
	while(left<=right) {
	    int mid = left + (right-left)/2;// 不能使用(right+left)，因为有可能整数溢出
	    if(mid <= x/mid) {
	    	left = mid + 1;
	    } else {
	    	right = mid - 1;
	    }
	}
	return left-1;
}