NoPX's blog

Binary search on doubles
By NoPX, history, 9 years ago, In English

Let's say I have boundaries left and right, which are doubles and I want to do binary search. How long should I iterate to be sure that given error isn't too big.

For example, in the last contest there was a problem http://codeforces.com/contest/579/problem/E

I saw some codes and authors use 100, 200 etc iterations

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

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

Lets say the left-right+1 is N and the absolute error mustn't exceed K you should iterate log2(N/K). Maybe a little more for sureness.

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

    I don't get the reason behind it ? Can you just elaborrate a bit ?

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

      For example if the error mus not exceed 10^(-7). It is just like multiplying the boundaries by 10^7 and getting rid of the floating points.I hope it helps and if you still confused feel free ask :D

      → Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

we can find the answer no more than 50 iterations. Because we can see, that when n = 200000 and we do n /= 2 50 times, answer approach maximize to 10 in -6. But in that problem you can see that need to use ternary search, wich need 120 iterations to have exact answer

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

    Ternary search is not necessary, you can still use binary :)

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

      your right, but NoPX write about authors parse or another users. I think he saw ternary search ;)

      → Reply
»
9 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Naturally for double value 50-60 iteration give AC in Online judge(in uva,lightoj). But to be more careful, in the contest time u can use 100/150/200 iteration based on your time limit. 100 iteration means u could find a number from a list of size 2^100 in 100 iteration. So for double value if the number is 10^18. still u have a enough iteration to correct the precision.

→ Reply