Arrange Coins

O(n)的算法太trivial了，没有什么意义，这里的算法是二分的，我们可以从1-n的上下界来二分，每次的中间值mid行的满行有多少点，拿这个点和n比较一下就能算出来了，二分模板真的什么情况都适用，只要最后尾部判断不复杂的话，这么写完全适应所有情况

class Solution(object):
    def arrangeCoins(self, n):
        """
        :type n: int
        :rtype: int
        """
        start, end = 1, n
        while start + 1 < end:
            mid = start + (end - start) / 2
            tmp = mid * (mid + 1) / 2
            if 0 <= n - tmp < mid + 1:
                return mid
            elif tmp > n:
                end = mid
            else:
                start = mid

        if 0 <= n - start * (start + 1) / 2 <= start + 1:
            return start
        return end