buzzvil's blog

tricky binary serach loop invariant question
By buzzvil, history, 8 years ago, In English

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?

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

Comments Comments (3)
| Write comment?
»
8 years ago, # |
← Rev. 6   Vote: I like it +1 Vote: I do not like it

UPD: previous claim was wrong. Maybe you try to return max of h-l instead of h-l+1 in the stated problem?

How I write binsearch, if there is at least one "YES", answer in [0, n-1]

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

    Hi, thanks for your input. I have a question

    1) because you write the while loop condition as "h -1 > l", it terminates when l, h are right next to each other. (i.e. h — 1>= l, or l+1<=h, but we know l < h, eventually l + 1 = h)

    2) The way you are halving the interval is equivalent to ensuring "the answer lies in [l, h) "

    So my question is in line 8 of your code, why check from h? 1) + 2) gauruntees that "h" cannot be an answer

    → Reply
    • »
      »
      »
      8 years ago, # ^ |
      ← Rev. 4   Vote: I like it +1 Vote: I do not like it

      I've looked again at your binsearch pseudocode — it looks OK (overlooked that right bound is exclusive, my pseudocode used inclusive bounds).

      19061181 if cumsum[idx + candidate] - cumsum[idx - 1] <= k: checks that in range [idx, idx+candidate] there will be at most k changes. But length of interval is candidate + 1, not candidate. Also, you rebuild your array cumsum on every binary search.

      → Reply