Skip to content

Instantly share code, notes, and snippets.

@jianminchen
Created April 29, 2018 03:56
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save jianminchen/e36ab48984c382c4b074eba425c8d336 to your computer and use it in GitHub Desktop.
Save jianminchen/e36ab48984c382c4b074eba425c8d336 to your computer and use it in GitHub Desktop.
Root of a number - apply binary search - being an interviewer
#include <stdio.h>
#include <stdlib.h>
#include<math.h>
double binarySearch(double l,double r,double x,unsigned int n)
{
// printf("%lf %lf \n",l,r);
if(r >= l)
{
double mid=l + (r-l)/2;
double m1 = pow(mid,n); // ?
printf("%lf %lf %lf",l,r,mid);
printf(" m1 - %lf \n",m1);
if(m1 > x) //|y-root(x,n)| < 0.001)
{
return binarySearch(l,mid - 0.001,x,n); // 1.625 ^2 = 2.6406 < 3
}
else
{
if(x-m1 < 0.001)
{
return mid;
}
else
return binarySearch(mid + 0.001,r,x,n);
}
}
return r;
}
void root(double x, unsigned int n, double *out)
{
int i=1, x1 = 0;
while(x1<x) // x = 4, n = 2, x1 = 0
{
x1=pow(n,i);
i++;
}
/* 0 - upper bound Math.Max(x, 1) */
if(x1==x)
{
*out=i-1;
return;
}
else{
double l=i-2,r=i-1;
*out=binarySearch(l,r,x,n);
}
// your code goes here
}
int main() {
return 0;
}
/*
given x = 7, n = 3, how do you find the root?
guess root = 1, 1 ^3 = 1 < 7
guess root = 2, 2^3 = 8 > 7
then we know that the answer should between 1 and 2 ->
1 2
--------------- <-, 0.001
1, 1.001, 1.002, ..., 2 -> 1000 to search to see if which one is the answer -> */
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment