(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:

- Process the middle element

- Call the same function with the left half

- Call the same function with the right half

void foo(int * arr, size_t length)
{
    if (!length) {
        return;
    }

    // Process the middle element
    process(arr[length / 2]);

    // Handle the left side
    foo(arr, length / 2);

    // Handle the right side (+1 to skip the middle element)
    foo(arr + length / 2 + 1, /* ??? */);
}

What should be the length of the right half on the last line? Minus 1 for the already-processed middle element and minus length/2 for the left half:

  a)    length - 1 - length / 2

That seems to be correct. Then I simplified:

  b)    length / 2 - 1

And that was a mistake because b produces size_t.max when length==1 to begin with. So, the calculations a and b are not equivalent. You knew it already ;) but it surprised me today.

Also, this is not an issue with D's slices because slices remove the need for such calculations:

    foo(arr[$ / 2 + 1 .. $]);    // Simple and correct

Which also means that maybe I should have used a pair of pointers in the original function instead of a pointer and a length.

Ali

On Fri, 04 Apr 2014 18:30:28 -0400, Ali Çehreli <acehreli@yahoo.com> 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