tricky binary serach loop invariant question

Revision en3, by buzzvil, 2016-07-13 06:39:47

Hi all,

I've read a lot about binary search and its notorious tricky nature to implement correctly. One thing I learned over time is thinking in loop invariants helps with proving your code's correctness. I recently solved a problem on binary search and got AC but I fail to see why my code works correctly

link: http://codeforces.net/problemset/problem/676/C

For this problem, we have to find the longest substring that consists of the same letter (either 'a' or 'b') IF you can change 'a's to 'b's or vice versa up to K times.

I solved the problem separately for 'a's and 'b's, then returned the maximum of two.

Let me elaborate what I did for one letter 'a' (it's identical for the other character)

If I had a magic function that tells me "can you find a candidate answer of length L", what I am looking for is

for given array A of length N

YES, YES, YES, ...., YES, NO, NO, NO, ..., NO

I need to find the last index (or longest length) that says YES.

to find such an index using binary search, I maintain the following loop invariants,

1) l < h and initially, l = 0, h = n

2) call that magic function P, then always, P(l) = True and P(h) = False. put another way, answer lies in interval [l, h)

3) the while loop continues as long as "l + 1 < h". so, when it terminates, l + 1 >= h, but combined with 1) we know l + 1 = h.

4) because of 2), we know that the answer must be l

translated to pseduo-code,

http://ideone.com/uvLw0s

But the answer this code gives is always one less than the actual answer. When I return h instead of l (because i'm 1 off), I get AC. But following my lines of logic, I know it must be 'l' that is the answer. Can you guys help me with finding a flaw in my logic?

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en3 English buzzvil 2016-07-13 06:39:47 4
en2 English buzzvil 2016-07-13 06:38:13 188
en1 English buzzvil 2016-07-13 06:36:41 1831 Initial revision (published)