Codeforces and Polygon may be unavailable from December 6, 19:00 (UTC) to December 6, 21:00 (UTC) due to technical maintenance. ×

fofao_funk's blog

Doubt about Binary Search
By fofao_funk, history, 9 years ago, In English

Hi.

I was looking some solutions of problem 551C - GukiZ hates Boxes and I found this one: 11548616.

Basically, the code binary search the optimal time. One thing I can't understand is its stop condition (and then the choice of the optimal answer). The while stop condition in the main function is ma - mi > 1, i.e., it will stop when mi + 1 = ma and (I think) there will never be such case that mi = ma. After that while, he prints the value of ma (right 'pointer' of binary search).

My doubt is: why can't mi be the optimal answer? How is he sure that ma is already the optimal answer despite the fact that mi is still inside the 'search' range?

Any help is appreciated. Thanks!

  • Vote: I like it
  • 0
  • Vote: I do not like it

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

Because mi is actually never in the search range. It starts with an invalid value (0), and only receives invalid values from there.

But really, when it comes to binary search, I guess the best thing is sticking with what works for you.

→ Reply