I m learning binary search and here i need to find the nth root of a number ,i am not able to figure out the error in the below program please help. I am getting answer wrong when x is between 0 and 1 ,I don't know why binary search is not working for in that case can someone explain? eg test case 0.09 3,whhy bs is not able to converge for l=0 and x=0.09?
#include <iostream>
#include <vector>
#include<algorithm>
#include<iomanip>
using namespace std;
double solve(double x, int n){
int iter=200;
double low=0;
double high=x;
while(iter--){
double mid = (low+high)/2;
//cout<<mid<<endl;
double val = pow(mid,n);
cout<<val<<endl;
if(val<x)low=mid;
else high=mid;
}
return low;
}
int main() {
// int t--;
int t;
cin>>t;
while(t--){
double x;
cin>>x;
int n;
cin>>n;
cout<<fixed<<setprecision(12)<<solve(x,n)<<endl;
}
return 0;
}
Consider $$$x$$$ to be in the interval $$$[0,1)$$$. Then the limits of your binary search should be $$$lo=x$$$ and $$$hi=1$$$.
can you explain it why ?
Take for example $$$\sqrt{0.5} = 0.7071$$$ which is greater than $$$0.5$$$. Why happen this? If you multiply a number by one, something less than than one or something greater than one it will remain equal, get small or get bigger respectively. So if you want to find the number $$$y$$$ which $$$y^n = x$$$ and $$$x$$$ in $$$[0,1)$$$ you can be sure that $$$y$$$ should be in $$$[x,1]$$$.
But same apply for lo=0 ans hi=x its nth root will lie in range [0,x) and Binary search is not working for this it is more intuitive too why it is not working can you help?
I'm not sure if I understood you. In the case of $$$x$$$ in $$$[1, \infty )$$$ you should set $$$lo = 1$$$ and $$$hi=x$$$.
Look to output of
for (double x = 0; x < 1; x += 0.1) cout << pow(x, n);
. I think you will see the issue.can you be more specific?I didn't get you.
Look at the series. You are trying to find a value that is out of range due to wrong upper bound you have set in the algorithm.