acash's blog

By acash, history, 4 years ago, In English

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;
}
  • Vote: I like it
  • -9
  • Vote: I do not like it

| Write comment?
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Consider $$$x$$$ to be in the interval $$$[0,1)$$$. Then the limits of your binary search should be $$$lo=x$$$ and $$$hi=1$$$.

  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    can you explain it why ?

    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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]$$$.

      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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?

        • »
          »
          »
          »
          »
          4 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          I'm not sure if I understood you. In the case of $$$x$$$ in $$$[1, \infty )$$$ you should set $$$lo = 1$$$ and $$$hi=x$$$.

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Look to output of for (double x = 0; x < 1; x += 0.1) cout << pow(x, n);. I think you will see the issue.

  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    can you be more specific?I didn't get you.

    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      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.