# Divide two quantity utilizing Binary search with out utilizing any / and % operator

Given two integers one is a dividend and the opposite is the divisor, we have to discover the quotient when the dividend is split by the divisor with out the usage of any ” / “ and ” % “ operators.

Examples:

Enter: dividend = 10, divisor = 2
Output: 5
Rationalization: 10/2 = 5.

Enter: dividend = 10, divisor = 3
Output: 3
Rationalization: 10/3 = 3.33333… which is truncated to three.

Enter: dividend = 10, divisor = -2
Output: -5
Rationalization: 10/-2 = -5.

Method: To resolve the issue utilizing Binary Search observe the under thought:

We already know that Quotient * Divisor ≤ Dividend and the Quotient lie between 0 and Dividend. Due to this fact, we are able to assume the Quotient  as mid, the Dividend as greater certain and 0 because the decrease certain and may simply use binary search to fulfill the phrases of division which is Quotient * Divisor ≤ Dividend.

Comply with the steps to unravel the issue:

• At first, set excessive = dividend and low  = 0 .
• Then, we have to discover the mid ( i.e Quotient ) = low + (excessive – low ) / 2 .
• Then, we carry out Binary Search within the vary of 0 to the dividend.
• If mid * divisor > dividend, then replace excessive = mid – 1 .
• Else  we replace low = mid + 1
• The worth of mid which satisfies the situation (i.e mid * divisor ≤ dividend) is our Quotient.
• Then, we return it by checking the Parity.

Under is the implementation of the above method:

## C++

 ` `  `#embrace ` `utilizing` `namespace` `std;` ` `  `int` `divide_binary_search(``int` `dividend, ``int` `divisor)` `{` `    ` `    ``if` `(dividend == divisor)` `        ``return` `1;` ` `  `    ` `    ` `    ` `    ``if` `(dividend == INT_MIN && divisor == 1)` `        ``return` `INT_MIN;` ` `  `    ` `    ` `    ` `    ` `    ` `    ``else` `if` `(dividend == INT_MIN && divisor == -1)` `        ``return` `INT_MAX;` ` `  `    ` `    ` `    ``lengthy` `lengthy` `low = 0, excessive = ``abs``(dividend), mid;` ` `  `    ` `    ``int` `quotient = 0;` ` `  `    ``whereas` `(low <= excessive) {` ` `  `        ` `        ``mid = low + (excessive - low) / 2;` ` `  `        ` `        ``if` `(``abs``(mid * divisor) > ``abs``(dividend))` `            ``excessive = mid - 1;` ` `  `        ` `        ``else` `{` `            ``quotient = mid;` `            ``low = mid + 1;` `        ``}` `    ``}` ` `  `    ` `    ` `    ``if` `((dividend < 0 && divisor < 0` `         ``|| dividend > 0 && divisor > 0))` `        ``return` `quotient;` `    ``else` `        ``return` `-quotient;` `}` ` `  `int` `primary()` `{` `    ``int` `dividend = 10, divisor = 2;` ` `  `    ` `    ``cout << ``"The Quotient is : "` `         ``<< divide_binary_search(dividend, divisor);` ` `  `    ``return` `0;` `}`
Output

`The Quotient is : 5`

Time Complexity: O(log N), as Binary Search algorithm is used.
Auxiliary House: O(1), since no further house has been used.