Off by one errors / Edge Cases in Binary Search/ 2-Pointer Technique

Правка en5, от viralm, 2017-01-27 10:22:31

Often when trying to solve a problem involving Binary Search or 2-Pointer Technique, I make off by one errors, and/or fail to handle edge cases. Even if I know that my solution might fail on a particular edge case, to correct it takes a lot of time. I would like to know a method/implementation, such that I can code up the solutions without having to worry about edge cases, etc. For Binary Search, I know of one such method where to avoid infinite loop, we can use the following code: Say we want to find the maximum index in an array which satisfies certain property -->

while(hi-lo>1)
{
    int mid=(lo+hi)/2;
    int chk=check(mid);
    if(chk==1) lo=mid;
    else hi=mid-1;
}
int ans;
if(check(hi)==1) ans=hi;
else ans=lo;

If any better approach is available(for Binary Search), you are welcome to comment. Also, can you give a good implementation for 2 — Pointer Technique.

Thanks in advance.

Теги binary seach, two-pointers, implementation

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en5 Английский viralm 2017-01-27 10:22:31 127
en4 Английский viralm 2017-01-27 10:10:29 16 Tiny change: 'nif(check(SOME CONDITION)==1) ans=' -> 'nif(check(hi)==1) ans='
en3 Английский viralm 2017-01-27 10:09:50 17 Tiny change: 'chk=check(SOME CONDITION);\n if' -> 'chk=check(mid);\n if'
en2 Английский viralm 2017-01-27 10:01:41 6 Tiny change: 'hi;\nelse mid=lo;\n~~~~' -> 'hi;\nelse ans=lo;\n~~~~'
en1 Английский viralm 2017-01-27 08:12:08 1157 Initial revision (published)