[leetCode] Sqrt(x)

Implement int sqrt(int x).

Compute and return the square root of x.

思路：

整数近似平方根 y = sqrt(x)，则：y^2 <= x < (y+1)^2，或y <= x/y < y+1，并且0 <  y <= x

二分法查找：start = 0, end = x, mid = (start+end)/2

问题转化成一个sorted序列 1^2, 2^2, 3^2, ... x^2
寻找y满足y^2 = x，如果不存在这样的y，则寻找y使x插入该序列时，y^2为x前一个元素。这样问题转化为Insertion Position那题的变种。区别仅仅在于base case

(1) x/mid = mid：return mid

(2) x/mid < mid：end = mid-1

(3) x/mid > mid：start = mid+1

之所以用x/mid来判断是为了防止overflow

base case：当y^2 = x不存在，即x为非完全平方数
(1) start = end = mid：
(a) mid^2 < x，此时mid应为结果。下一步start = mid+1, end = mid，查找结束，此时应返回end
(b) mid^2 > x，此时mid-1应为结果。下一步start = mid, end = mid-1，查找结束，此时应返回end

(2) start = end-1 = mid：
mid^2 < x，下一步start = mid+1, end = mid，进入(1)的情况
mid^2 > x，此时mid-1应为结果。下一步start = mid, end = mid-1，查找结束，此时应返回end

综上所述：查找结束后：return end

Corner case: 

(1) x<0，return -1表示出错（需要和面试官讨论）。

(2) x=0或1，此时mid=0，会形成x/y = 0/0。需要特殊处理。

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17

class Solution { public: int sqrt(int x) { if(x<=1) return x; int start=0, end=x; while(start<=end) { int mid = start + (end-start)/2; if(x/mid==mid) return mid; else if(x/mid<mid) end = mid-1; else start = mid+1; } return end; } };

总结：这里有必要总结下binary search的一个规律
当x不存在于一个sorted array A[0:n-1]中时，binary search的循环必然会因为start > end而终止。此时必然有：A[end] < x < A[start]，如果end >=0 且 start<n。

这也就是为什么这题需要返回end，而Insertion Position那题却要返回start的原因。