Standard binary search method in Java


  • 0
    L
    public class Solution {
    public int sqrt(int x) {
        if (x == 0) return 0;
        if (x < 0) return -1;
        int lo = 1, hi = x;
        while (lo <= hi) {
            int mid = (lo + hi) >> 1;
            if (mid == x / mid) {
                return mid;
            } else if (mid < x / mid) {
                lo = mid + 1;
            } else {
                hi = mid - 1;
            }
        }
        return hi;
    }
    

    }

    Since all binary search can come to the case where lo == hi if an appropriate value is not yet found, if (lo * hi > x) and hi is decremented by 1, hi should then be the answer.


Log in to reply
 

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