twoslow's blog

By twoslow, 5 months ago, In English,

The two Pointer algorithm is quite popular technique. Although the idea is straightforward, Its implementation is prone to bugs. Few such bugs includes:

  • Index out of range error leading to SEGSEV
  • Never ending while loops leading to SIGKILL

How to write in a way such that there is less chances of bugs?

This blog is a sister blog of Binary Search Elegant Implementation. Your thoughts and implementations are valuable to community, hence welcome.


Thanks. Have a great time ahead!

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

»
5 months ago, # |
Rev. 5   Vote: I like it +43 Vote: I do not like it
for (int l = 0, r = 0; l < n; remove(l++)) {
    while(!ok())
        add(r++);

    if(r > n + 1)
        break;

    // do something with segment [l, r), that is ok()
}
  • »
    »
    5 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Can you explain a little bit about your code ?

»
5 months ago, # |
  Vote: I like it -12 Vote: I do not like it
int a = 1, b = 1;
while (a <= n && b <= m) {
if (something1) {
 a++;
 // calc ans...
} else if (something2) {
 b++;
 // calc ans...
} else {
// may be
 a++;
 b++;
}
}
while (a <= n) {
 a++;
 if (something1) {
 // calc ans...
 }
}
while (b <= m) {
 b++;
 if (something2) {
 // calc ans...
}
}
»
5 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Copy tourist's code.