sqrt(x)

sqrt(x)

Special binary search problem

Left bound is zero, and right bound is max(x/2,1). Then do the binary search to find out the result. Some corner cases should be taken care of.

  • When the target is 1, so we usemax(x/2,1).
  • When we caculate mid*mid, this may beyond the bound ofint, we need uselong longinsteand ofint.
  • When we write the comparative expression, put long long at left.
 1 class Solution {
 2 public:
 3     int sqrt(int x) {
 4         long long left = 0;
 5         long long right = max(x/2,1);
 6         long long mid = 0;
 7         while ( left <= right ) {
 8             mid = left+(right-left)/2;
 9             if ( mid*mid > x ) {
10                 right = mid-1;
11             }
12             if ( mid*mid == x ) {
13                 return mid;
14             }
15             if ( mid*mid < x && (mid+1)*(mid+1) > x ) {
16                 return mid;
17             }
18             if ( (mid+1)*(mid+1) == x ) {
19                 return mid+1;
20             }
21             if ( (mid+1)*(mid+1) < x ) {
22                 left = mid+1;
23             }
24         }
25     }
26 };

Loading Disqus comments...
Table of Contents