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.com/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,
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?
