# 29\_Divide Two Integers

\[Medium] \[Math, Binary Search]

Given two integers `dividend`and `divisor`, divide two integers without using multiplication, division and mod operator. Return the quotient after dividing `dividend`by `divisor`. The integer division should truncate toward zero.

**Example 1:**

```
Input: dividend = 10, divisor = 3
Output: 3
```

**Example 2:**

```
Input: dividend = 7, divisor = -3
Output: -2
```

## Solution 1: Linear Search

**Idea**:

* Deduct divisor from dividend many times. Record how many times it takes until dividend is less than divisor.

**Time Complexity**: $$O(n)$$, where n is the output (quotient).

**Space Complexity**: $$O(1)$$

```python
def divide(dividend, divisor):
    """
    :type dividend: int
    :type divisor: int
    :rtype: int
    """
    positive = (dividend < 0) == (divisor < 0)             
    dividend, divisor = abs(dividend), abs(divisor)

    output = 0
    while dividend >= divisor:
        output += 1
        dividend -= divisor

    if not positive:
        return max(-output, -2147483648)
    else:
        return min(output, 2147483647)
```

## Solution 2: Binary Search ??

整数近似除法：32/3 = 10

显然求近似除法可以用乘法来二分查找：32 \~ 3\*10 = 3\*\[1\*(2^3) + 0\*(2^2) + 1\*(2^1) + 0\*(2^0)]

res = 0

1. 先找到a使x\*2^a <= y < x\*2^(a+1)，res += 2^a，y = y - x\*2^a
2. if(y >= x\*2^(a-1) {res+=2^(a-1); y = y - x\*2^(a-1);}
3. if(y >= x\*2^(a-2) {res+=2^(a-2); y = y - x\*2^(a-2);}

...

但题目不允许用乘法，可以用移位代替：x\*2^i = x<\<i：

**Time Complexity**: $$O(\log{n})$$, where n is the output (quotient).

**Space Complexity**: $$O(1)$$

```python
def divide(dividend, divisor):
    """
    :type dividend: int
    :type divisor: int
    :rtype: int
    """
    positive = (dividend < 0) is (divisor < 0)
    dividend, divisor = abs(dividend), abs(divisor)
    res = 0
    while dividend >= divisor:
        temp, i = divisor, 1
        while dividend >= temp:
            dividend -= temp
            res += i
            i <<= 1
            temp <<= 1
    if not positive:
        res = -res
    return min(max(-2147483648, res), 2147483647)
```