Ruby Binary Search Solution


  • 0
    I

    We could use Binary Search on Result to get sqrt(x) in O(logn) time.

    Code:

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

    Thanks to @StefanPochmann, I get to know the Newton's Method. Here is the post 3-4 short lines, Integer Newton, Every Language as a note for me.


Log in to reply
 

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