Share my easy & simple Java Binary Search Solution


  • 1
    public class Solution {
        public int arrangeCoins(int n) {
            int lo = 0, hi = n;
            while(lo<=hi){
                long mid = lo + (hi-lo)/2, a = (1+mid), b = (2+mid);
                if(a*mid/2<=(long)n && a*b/2>(long)n) return (int)mid;
                else if(a*mid/2>(long)n) hi = (int)mid-1;
                else lo = (int)mid + 1;
            }
            return lo;
        }
    }
    ``

  • 0
    Z

    why don't you use
    mid = ( low + high ) / 2

    low + ( high -low)/2 == (low + high) /2 ?


  • 0
    T

    @zebra1831 to prevent integer overflow. left + right could overflow, whereas right - left couldn't.


Log in to reply
 

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