Division of Two Numbers using Binary Search Algorithm

In this post, we will discuss division of two numbers (integer or decimal) using Binary Search Algorithm.


 

 
We can easily modify Binary Search algorithm to perform division of two decimal numbers. We start by defining range for our result as [0, ULONG_MAX] which serves as initial low and high for the binary search algorithm. Now we need to find a mid that satisfies x / y = mid or x = y * mid for given two numbers x and y and that will be our result.

Based on comparison result between x and y * mid, we either update low, update high or return mid –

  1. If y * mid is almost equal to x, we return mid.
     
  2. If y * mid is less than x, we update low to mid.
     
  3. If y * mid is more than x, we update high to mid.
     

We also need to take care of few conditions like divisibility by 0, sign of the result, etc as demonstrated in below C++ program:

C

Download   Run Code

Output:

3.142822

Java

Download   Run Code

Output:

3.1428222656249996

 
The time complexity of above solution is O(log(n)) where n is equal to ULONG_MAX in C or Double.MAX_VALUE in Java.

 
Thanks for reading.

Please use ideone or C++ Shell or any other online compiler link to post code in comments.
Like us? Please spread the word and help us grow. Happy coding 🙂
 

Leave a Reply

avatar
  Subscribe  
Notify of