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

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

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

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

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

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