Блог пользователя twoslow

Автор twoslow, 6 лет назад, По-английски

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!

  • Проголосовать: нравится
  • +21
  • Проголосовать: не нравится

»
6 лет назад, # |
Rev. 5   Проголосовать: нравится +43 Проголосовать: не нравится
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()
}
»
6 лет назад, # |
  Проголосовать: нравится -12 Проголосовать: не нравится
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...
}
}
»
6 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

Copy tourist's code.