Division of Two Numbers using Binary Search Algorithm

In this post, we will discuss division of two numbers (integer or decimal) using Binary Search (Divide and Conquer) 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.14282

The time complexity of above solution is O(log(n)) where n is equal to ULONG_MAX.

 
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

Notify of
avatar
wpDiscuz