Wednesday, July 31, 2013

Finding the square root (of a perfect square) using binary search c#

Well, the logic is pretty straightforward. We start a binary search from a range of 0 to NUM, where NUM is the number whose root we are looking for. Each time, we calculate the middle item of the range and see if it is the square root. If not, we search further either in the right side or the left side of the mid item depending on whether the mid^2 is lesser or greater than NUM.



[code language="cpp"]
double GetRoot(double Num,double High=0, double Low=0)
{
if(High<Low || High-Low==1) return -1; //End case
if(High==Low && Low==0) High=Num; //Start case
int Mid= Low+((High-Low)/2);
if(Mid*Mid==Num) return Mid;
else
{
if(Mid*Mid>Num) return GetRoot(Num,Mid,Low);
else if(Mid*Mid<Num) return GetRoot(Num,High,Mid);
}
}

[/code]


If you have thoughts/ suggestions, post em on comments.

3 comments:

  1. I would suggest use a double instead of an int as it is a square root problem so that it solves more cases

    ReplyDelete
  2. Hello! Do you use Twitter? I'd like to follow you if that would be okay.
    I'm definitely enjoying your blog and look forward
    to new updates.

    ReplyDelete

GraphQL

GraphQL What is GraphQL It is a specification laid out by Facebook which proposed an alternative way to query and modify data. Think o...