# Solve this problem with Binary Search

• ``````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;
}
};``````

• I used the similar way to binary search it, the difference is I used if (mid*mid <= x) instead of if (mid <= x / mid), but I got TLE...Does anybody know why?

• mid * mid will overflow when mid > sqrt(INT_MAX)

• Thanks a lot!

• @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 update `ans` 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+(end-start)/2;
if(mid*mid==x)
return mid;
else
if(mid*mid<x)
start=mid+1;
else
end=mid-1;
}

return mid;
}
};
``````

• @BatCoder There're two points I need to explain a bit.

Firstly, the rationale behind `mid <= x / mid` instead of using `mid * mid <= x` is just for preventing from overflow (multiply two `int` numbers may not fit in `int` as well).

Secondly, the meaning of `ans` in my code is used to keep the biggest integer which satisfies `ans * 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 satisfy `mid * mid <= x` cause you never know which branch of conditions `mid` 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 satisfies `ans * ans <= x`.

Hope this help.

BR

• @Stomach_ache This is helpful, thank you! :)

• @Stomach_ache Excellent explanation of the nuances of this algorithm. Thank you.

• Actually I think 'right' can be set to (x/2) at the beginning. Because sqrt of a number will always be smaller or equal to 1/2 of this number. So the range of binary search can be set to (1, x/2). The running time should be better

• @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.

• Similar idea, a little cleaner implementation. I used the trick `m=(l+r+1)/2`, something I learned from others on Leetcode, basically to tilt the mid calculations towards to the right (instead of to the left from default c++ integer division flooring).

``````int mySqrt(int x) {
int l=0,r=x;
while (l<r) {
int m=(l+r+1)/2;
if (m>x/m) r=m-1;
else l=m;
}
return r;
}
``````

• I don't see why `mid` is supposed to be calculated in the following way.

`int mid = left + (right - left) / 2;`
I confirmed that the code works, but I don't see why `mid` can't be produced by something like
`int mid = (right + left) / 2;`

Could you explain a bit more about it?

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.