On Fri, 04 Apr 2014 18:30:28 -0400, Ali Çehreli <[email protected]> wrote:
(This was in C and probably a common mistake that I haven't experienced
until today.)
tldr; The following two expressions are not equivalent:
a) length - 1 - length / 2
b) length / 2 - 1
I was trying to write a recursive function similar to binary search:
...
I have implemented binary search many many times. Almost EVERY time,
things like this get me. Generally, it ends up getting stuck in an
infinite loop in some corner cases. It's one of those things where it
seems so simple in concept, but ends up being so tricky to implement, and
even harder to test.
I think your idea of using pointers is a good one.
But another rule of thumb I like to follow -- try not to be too clever
when dealing with tricky code :) Brevity does not always equal quality:
unsigned int midpoint = length / 2;
// Process the middle element
process(arr[midpoint]);
// Handle the left side
foo(arr, midpoint);
// Handle the right side
++midpoint;
foo(arr + midpoint, length - midpoint);
-Steve
