Codeforces и Polygon могут быть недоступны в период с 6 декабря, 22:00 (МСК) по 7 декабря, 00:00 (МСК) в связи с проведением технических работ. ×

Doubt about Binary Search

Правка en4, от fofao_funk, 2016-03-16 03:45:19

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!

Теги binary search, doubt

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en4 Английский fofao_funk 2016-03-16 03:45:19 8 Tiny change: ' when `mi = ma + 1` and (I t' -> ' when `mi + 1 = ma` and (I t'
en3 Английский fofao_funk 2016-03-16 03:05:20 25 Tiny change: 'r despite `mi` being inside th' -> 'r despite the fact that `mi` is still inside th'
en2 Английский fofao_funk 2016-03-16 03:01:19 5 Tiny change: 'such case such that `mi ' -> 'such case that `mi '
en1 Английский fofao_funk 2016-03-16 03:00:19 726 Initial revision (published)