Блог пользователя acash

Автор acash, история, 4 года назад, По-английски

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;
}
  • Проголосовать: нравится
  • -9
  • Проголосовать: не нравится

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    can you explain it why ?

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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 года назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        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 года назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          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 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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