LeetCode解题报告(29)--通过加法完成除法

原题如下： >Divide two integers without using multiplication, division and mod operator.

If it is overflow, return MAX_INT.

题目要求返回一个数除以另外一个数的结果，并且要求不能用乘除或取模，意思就是只能用加减，用加减也不难，先初始化sum=0，每次sum加上除数的大小并与被除数比较，直到sum大于等于被除数即可。但是这样的时间复杂度是\(\Theta(n)\)，提交时会超时。

解决思路是采用二分搜索，或者说变形的二分搜索。思路类似于上面所说的，但是sum每次加上自己的大小，也相当于sum=sum*2,这样的时间复杂度是\(\Theta(log_2n)\),提交时能够AC

实现的代码如下：

class Solution(object):
    def divide(self, dividend, divisor):
        """
        :type dividend: int
        :type divisor: int
        :rtype: int
        """
        MAX_INT = pow(2,31)-1
        if divisor == 0:
            return MAX_INT
    
        flag = 1
        if (dividend > 0 and divisor<0 ) or (dividend<0 and divisor >0):
            flag = -1
        a = abs(dividend)
        b = abs(divisor)
        res = 0
        while a >= b :
            sum = b
            count =1 
            while a >= sum+sum:
                sum += sum
                count += count
            a-=sum
            res+=count
        if res*flag > MAX_INT:
            return MAX_INT
        else:
            return res*flag