一种在某些约束下除以2的有效方法

Question

这是我在进行二进制搜索时遇到的一个问题。这是问题所在：

给出两个整数被除数和除数，将两个整数相除而不使用乘法，除法和mod运算符。

除以除数后的商。整数除法应截断为零。

注意：

1。除数和除数均为32位有符号整数。

2。除数永远不会为0。假设我们正在处理的环境只能存储32位有符号整数范围内的整数：[− 2 ^ 31，2 ^ 31 − 1]。

3。出于这个问题的目的，假设除法结果溢出时您的函数返回2 ^ 31 − 1。

蛮力解

是用除数减去除数，直到除数更大为止，然后得出减数。但是它给出了超过时间限制错误。

现在我已经应用了[[二进制搜索，但是它使用了乘法运算符

。正如问题所言，我必须不使用*，/，mod来解决这个问题。

def divide( dividend, divisor):
    """
    :type dividend: int
    :type divisor: int
    :rtype: int
    """
    if divisor == 0 or (dividend == -2147483648  and divisor == -1)  :
        return 2147483647
    if divisor == 1 : 
        return dividend
    if divisor == -1 : 
        return -dividend

    sign = 1 if (dividend > 0 and divisor > 0) or (dividend < 0 and 
    divisor < 0) else -1


    dividend = abs(dividend)
    divisor = abs(divisor)

    res=0
    left=0
    right=dividend

    while left<=right:
        mid=(left+right)//2

        if mid*divisor== dividend:
            res=mid
            break
        elif mid*divisor<dividend:
            res=mid
            left=mid+1
        else:
            right=mid-1
    return res*sign

还有其他方法可以更有效地解决这个问题吗？

更新1：

我找到了解决方案。但是我有一些

时间复杂度部分有疑问

。请通过解决方案，让我知道。这是我在进行二进制搜索时遇到的一个问题。问题是：给定两个整数被除数和除数，将两个整数相除而不使用乘法，除法和mod运算符。 ...

Answer 1

我正在发布

解决方案，这里工作正常