LeetCode 69. Sqrt(x)

LeetCode 69. Sqrt(x)

Description:

Implement int sqrt(int x).

Compute and return the square root of x.

x is guaranteed to be a non-negative integer.

Example 1:

Input: 4
Output: 2

Example 2:

Input: 8
Output: 2
Explanation: The square root of 8 is 2.82842…, and since we want to return an integer, the decimal part will be truncated.

---

分析：

简单的一道题，但是要用二分搜索来解，一开始我没用二分搜索，直接一个for循环暴力破解，但要注意一个问题：两个数相乘是否越界！一开始用了int，遇到大数相乘越界了，答案错误，算是给我提个醒吧。
二分搜索的思想：将n个元素分成大致相等的两部分，取a[n/2]与x做比较，如果x=a[n/2],则找到x,算法中止；如果x<a[n/2],则只要在数组a的左半部分继续搜索x,如果x>a[n/2],则只要在数组a的右半部搜索x.
当然，这道题并不需要用到数组，由于规定了输入是一个int整型数，最大的int整型数为INT_MAX，比较中间数相乘以及中间数加1相乘与输入数x的大小即可，不断更新中间数，直至求解成功。

代码如下：

// bad solution
class Solution {
public:
	int mySqrt(int x) {
		if (x == 0) return 0;
		for (long i = 1; i <= x; i++) {
			if (i * i <= x && (i + 1) * (i + 1) > x) {
				return (int)i;
			}
		}
	}
};

二分搜索代码如下：

// another solution
class Solution {
public:
    int mySqrt(int x) {
        long left = 0, right = INT_MAX, mid = 0;
        while (true) {
            long mid = left + (right - left) / 2;
            if (mid * mid <= x && (mid + 1) * (mid + 1) > x)
                return (int)mid;
            if (mid * mid < x)
                left = mid + 1;
            else
                right = mid - 1;
        }
    }
};