Posts Find Square Root (Binary Search Approach)
Post
Cancel

Find Square Root (Binary Search Approach)

Problem Description

Given a non-negative integer x, compute and return the square root of x. Leetcode: Sqrt(x)

Constraints:

0 <= x <= 2^31 - 1

Solution

The important part in this code is to realize that m*m can lead to overflow. To handle this, we can do:

m == x/m

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
    
    public int mySqrt(int x) {
        
        int l=1, h=x, root=0;
        
        while(l<=h){
            
            int m = (l+h)/2;
            
            if(m == x/m) return m; //m*m can lead to overflow. 
            
            if(m>x/m){
                h = m-1;
            }else{
                root = m;
                l = m+1;
            }
                
        }
        
        return root;
        
    }
    
}
This post is licensed under CC BY 4.0 by the author.