Codeforces celebrates 10 years! We are pleased to announce the crowdfunding-campaign. Congratulate us by the link https://codeforces.com/10years. ×

BanazadehAria's blog

By BanazadehAria, history, 9 months ago, In English,

Hi guys, This is the code for binary search on real and float numbers

#include<bits/stdc++.h>
using namespace std;

//We want to find an element which a<0.0000001

const float target = 0.0000001;

int main()
{
    float l=0.00000000,r=100000.00000000;
    cout << l << " " << r;
    while((r-l)>0.0000000001){
        float mid = (float)((l+r)/2);
        cout << mid << endl;
        if(mid>target) r=mid;
        else l=mid;
    }cout << l;
}

But it will stop when it reaches 10 to power -5 what can I do to make it go until 10 to power -18?

 
 
 
 
  • Vote: I like it
  • +3
  • Vote: I do not like it

»
9 months ago, # |
  Vote: I like it +3 Vote: I do not like it

Auto comment: topic has been updated by ContestFucker (previous revision, new revision, compare).

»
9 months ago, # |
  Vote: I like it +29 Vote: I do not like it

Instead of keeping the limitation on some difference, you can execute the binary search for some specific fixed number of times. Usually 250-300 iterations are good enough for required granularity.

So your code would be something like :-

int iterations = 0;
while(iterations < 300)
{
  // your binary search logic
  iterations++;
}
  • »
    »
    9 months ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    And what data type if I want up to 10 to power -18? (I tested float and it didn't work)

    • »
      »
      »
      9 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Accuracy between float and double is noticeably different. Accuracy of float is approximately $$$10^{-7}$$$ and double type supports accuracy to $$$10^{-15}$$$. So if you need calculation with big precision you should use double. More information about accuracy of types can be found here

      https://www.tutorialspoint.com/cplusplus/cpp_data_types.htm

  • »
    »
    12 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    How this works ? Could you please explain it a bit further ?