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

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

Can anyone suggest me a good blog for binary search on double ? I found these type of implementation on different blog but failed to manage explanation. Could anyone explain it please ?

Type 1:

#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;
}

Type 2:

int iterations = 0;
while(iterations < 300)
{
  // your binary search logic
  iterations++;
}
  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

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

This one is good

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

Thanks :D

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

Pashka goes into a lot of detail regarding the implementation issue you raised in your post. Look at his posts on EDU Binary Search. I suffered from the same EPS nightmare until I went through his tutorials.

First register for the EDU. Then: Link for the post

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

    Do you know why 100 iterations will always be sufficient?

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

      Because the maximal value for

      Unable to parse markup [type=CF_MATHJAX]

      is $$$2^{63}-1$$$. Even though binary search works in $$$O(\log n)$$$, there is not estimated value.

      Simple binary search on array for finding specific value may do more operations than exact $$$\log n$$$ value. For example,

      Unable to parse markup [type=CF_MATHJAX]

      does 3 operations, while

      Unable to parse markup [type=CF_MATHJAX]

      . Since, this is very small testcase, the difference is small too.
      • »
        »
        »
        »
        3 года назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        Can you explain with refernce to real numbers?

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

          let us say I want to search for a number in a range of width W.
          x lies somewhere in the range [0,W]. If I were to choose any random number in this range then max error possible is W.
          Everytime I choose the midpoint of the range and will discard a range with width exactly half of the current search range.

          Now width of search range after 1 iteration is W/2, so max error possible is W/2.

          After K-iterations max error possible is W/(2^(K-1))