class Solution {
public:
int sqrt(int x) {
if (0 == x) return 0;
int left = 1, right = x, ans;
while (left <= right) {
int mid = left + (right  left) / 2;
if (mid <= x / mid) {
left = mid + 1;
ans = mid;
} else {
right = mid  1;
}
}
return ans;
}
};
Solve this problem with Binary Search

@Stomach_ache I used the following approach, which is very similar to a basic binary search. However, it doesn't give me the correct output. Could you please let me know why you check for
mid <= x / mid
and updateans
anyway? What made you not use the typical binary search (like the way I have implemented it below)?class Solution { public: int mySqrt(int x) { if(x==0  x==1) return x; int start=0, end=x, mid=0; while(start<=end) { mid=start+(endstart)/2; if(mid*mid==x) return mid; else if(mid*mid<x) start=mid+1; else end=mid1; } return mid; } };

@BatCoder There're two points I need to explain a bit.
Firstly, the rationale behind
mid <= x / mid
instead of usingmid * mid <= x
is just for preventing from overflow (multiply twoint
numbers may not fit inint
as well).Secondly, the meaning of
ans
in my code is used to keep the biggest integer which satisfiesans * ans <= x
and then it'll be the answer at the end of binary search procedure.I noticed that you made
mid
as the final answer at the last line in your code, which may not satisfymid * mid <= x
cause you never know which branch of conditionsmid
will go at the last round of binary search.
And btw, the input is not necessary a perfect square number, so that's why you should keep the largest integer that satisfiesans * ans <= x
.Hope this help.
BR



@marriema Yes, that is right.
But that does not actually matter so much since in Binary Search, iteration range being doubled only means exactly one more iteration done. This is something worth mentioning in an actual interview, but not something likely to produce noticeable running time difference to an OJ.