(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
